Python如何高效求解预算约束下选购物品的最大收益问题

你描述的场景是典型的0-1背包问题，是动态规划的经典应用场景，专门针对「每个物品最多选1次、总容量不超过上限、求最大收益」的需求，时间复杂度为O(n*C)，其中n是物品数量，C是预算总额，相比你之前用的全排列枚举的O(2^n)复杂度，性能提升非常明显，即使物品数量到几百量级也能正常运行。

我们定义一个一维DP数组dp，其中dp[j]表示预算为j美元时能拿到的最大收益，推导规则如下：

• 初始化dp数组长度为预算+1，所有元素初始值为0
• 遍历每一件物品，对每个物品从后往前遍历预算（避免重复选择同一件物品）
• 对于每个预算j，如果当前物品的成本小于等于j，就判断选这个物品的收益dp[j - cost[i]] + gain[i]是不是比不选的收益dp[j]大，取大的更新dp[j]
• 最终dp[dollars]就是预算范围内的最大收益

def max_gain(dollars, cost, gain):
    dp = [0] * (dollars + 1)
    # 遍历每件物品
    for i in range(len(cost)):
        # 从后往前遍历预算，防止重复选同一件物品
        for j in range(dollars, cost[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - cost[i]] + gain[i])
    return dp[dollars]

# 示例测试
dollars = 10
cost = [5, 4, 1, 10]
gain = [7, 6, 4, 12]
print(max_gain(dollars, cost, gain)) # 输出17，和示例结果一致

• 时间复杂度：O(n * 预算)，n为物品数量，只要预算不是特别大（比如1e5以上）都能快速出结果
• 空间复杂度：O(预算)，普通场景下上述实现已经足够使用，特殊场景还可以通过滚动数组进一步优化空间

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