投资组合优化问题：优化O(n!)复杂度的解决方案

问题描述 #

我们有一组订阅类金融产品，每个产品具备以下属性：

• 日收益率：单位金额每日可获得的收益
• 最低可分配金额：参与该产品所需的最小资金
• 最高可分配金额：该产品接受的最大资金上限

目标是将给定的总资金分配到这些产品中，以获取最高总日收益。当前采用的暴力递归贪心算法复杂度为O(n!)，在生产环境的大数据量下运行效率极低，因此需要至少多项式复杂度的解决方案。曾尝试应用动态规划，但由于资金金额为实数（分配后剩余金额连续递减），难以实现离散化状态转移。

原O(n!)复杂度实现 #

以下是原暴力递归的Python代码实现：

from pprint import pprint
from decimal import Decimal as D
from dataclasses import dataclass

_RATE = D(1) / 365

@dataclass
class Product:
    name: str
    min: D
    max: D
    annual_rate: D  # 年化收益率
    daily_returns: D = None

    def __post_init__(self):
        # 计算日收益率
        self.daily_returns = (1 + self.annual_rate) ** _RATE - 1

@dataclass
class Allocation:
    product: Product
    amount: D
    daily_gain: D = None

    def __post_init__(self):
        # 计算该分配的每日收益
        self.daily_gain = self.product.daily_returns * self.amount

# 产品列表示例
PRODUCTS = [
    Product('低收益灵活', 1, 100, D('0.01')),
    Product('普通灵活', 1, 100, D('0.02')),
    Product('60天锁定期', 20, 30, D('0.04')),
    Product('90天锁定期', 20, 35, D('0.05')),
    Product('7天质押', 1, 10, D('0.07')),
]

# 递归尝试所有可能的分配方案，选择收益最高的
# 复杂度：O(n!)
def _allocator(amount, products, path):
    max_gain, best_alloc = D(0), path

    for i, product in enumerate(products):
        if product.min <= amount:
            # 取产品上限和剩余资金的较小值
            allocate_amount = min(product.max, amount)
            # 递归处理剩余资金和剩余产品
            sub_gain, sub_alloc = _allocator(
                amount - allocate_amount,
                products[:i] + products[i+1:],
                [*path, (product, allocate_amount)]
            )
            # 加上当前分配的收益
            sub_gain += allocate_amount * product.daily_returns
            # 更新最优解
            if sub_gain > max_gain:
                max_gain = sub_gain
                best_alloc = sub_alloc

    return max_gain, best_alloc

def balance_brute(amount, products):
    _, allocations = _allocator(amount, products, [])
    return [Allocation(p, a) for p, a in allocations]

# 测试暴力算法
allocs = balance_brute(D(100), PRODUCTS)
pprint(allocs)
print('总日收益:', sum(a.daily_gain for a in allocs))

多项式复杂度解决方案：贪心算法 #

算法思路 #

由于每个产品的边际收益恒定（每增加1单位资金，收益增加量等于该产品的日收益率），因此可以采用贪心策略，优先给日收益率最高的产品分配尽可能多的资金，具体步骤如下：

1. 将所有产品按日收益率从高到低排序，确保优先处理高收益产品。
2. 初始化剩余资金为总金额，创建空的分配结果列表。
3. 遍历排序后的每个产品：
   • 如果剩余资金小于产品的最低分配金额：跳过该产品（无法满足参与条件）。
   • 否则，计算可分配的金额：取产品最高上限与剩余资金的较小值（因剩余资金≥最低要求，故分配金额自然满足最低限制）。
   • 分配该金额到当前产品，更新剩余资金，并记录分配结果。
   • 如果剩余资金为0：提前终止遍历（资金已全部分配）。
4. 若遍历结束后仍有剩余资金，尝试分配给最低要求≤剩余资金的最高收益产品（极端场景兜底）。

复杂度分析 #

• 排序阶段：O(n log n)
• 遍历分配阶段：O(n)
• 总复杂度：O(n log n)，属于多项式复杂度，可高效处理大规模产品列表。

Python实现 #

from pprint import pprint
from decimal import Decimal as D
from dataclasses import dataclass

_RATE = D(1) / 365

@dataclass
class Product:
    name: str
    min: D
    max: D
    annual_rate: D  # 年化收益率
    daily_returns: D = None

    def __post_init__(self):
        self.daily_returns = (1 + self.annual_rate) ** _RATE - 1

@dataclass
class Allocation:
    product: Product
    amount: D
    daily_gain: D = None

    def __post_init__(self):
        self.daily_gain = self.product.daily_returns * self.amount

PRODUCTS = [
    Product('低收益灵活', 1, 100, D('0.01')),
    Product('普通灵活', 1, 100, D('0.02')),
    Product('60天锁定期', 20, 30, D('0.04')),
    Product('90天锁定期', 20, 35, D('0.05')),
    Product('7天质押', 1, 10, D('0.07')),
]

def balance_greedy(total_amount, products):
    # 按日收益率降序排序
    sorted_products = sorted(products, key=lambda p: -p.daily_returns)
    remaining = total_amount
    allocations = []

    for product in sorted_products:
        if remaining <= 0:
            break
        # 检查是否满足最低分配要求
        if remaining < product.min:
            continue
        # 计算可分配的金额：不超过产品上限，不超过剩余资金
        allocate_amount = min(product.max, remaining)
        allocations.append(Allocation(product, allocate_amount))
        remaining -= allocate_amount

    # 兜底处理：剩余资金分配给符合最低要求的最高收益产品
    if remaining > 0:
        for product in sorted_products:
            if product.min <= remaining:
                allocations.append(Allocation(product, remaining))
                remaining = 0
                break

    return allocations

# 测试贪心算法
greedy_allocs = balance_greedy(D(100), PRODUCTS)
pprint(greedy_allocs)
print('总日收益:', sum(a.daily_gain for a in greedy_allocs))

结果验证 #

对比暴力算法和贪心算法的结果，会发现两者的总日收益完全一致——因为贪心策略在这种线性目标函数的约束下是最优的。例如对于100元测试资金，贪心算法会优先分配10元到7天质押（最高收益率），35元到90天锁定期，30元到60天锁定期，剩余25元到普通灵活产品，最终收益与暴力算法完全相同。

为什么动态规划不适用？ #

动态规划通常需要将状态离散化（比如按整数金额划分状态），但由于资金是实数，离散化会导致状态数量爆炸（精度越高，状态数越多），无法在合理时间内完成计算。而贪心算法直接利用边际收益恒定的特性，无需离散化，完美适配实数金额的场景。

内容的提问来源于stack exchange，提问作者Daniel