背包问题避坑实录：云主机预算内最优选配

问题背景：预算固定，云主机该怎么选

团队申请到一笔 10000 元年度云预算，需要在多款云主机套餐中做选择。每个套餐只能购买一次，价格不同，能承载的业务评分也不同。目标很明确：总价格不超过预算，让业务收益最大。

这类“每种物品最多选一次”的组合优化，就是经典的 0-1 背包问题（knapsack）。它看似是面试题，实际广泛出现在资源采购、广告投放、任务调度、容量规划等场景。

先给出本题的形式化定义：

• 有 n 个套餐，第 i 个套餐价格为 cost[i]，业务价值为 value[i]；
• 每个套餐最多选择一次；
• 总预算为 budget；
• 求不超过预算时能够获得的最大价值。

示例：

预算 budget = 10
价格 costs  = [2, 3, 4, 5]
价值 values = [3, 4, 5, 6]

最优方案是选择价格 2 + 3 + 5 = 10 的套餐，价值为 3 + 4 + 6 = 13。

方案对比：暴力枚举为什么不可行

方案一：枚举所有子集

每个套餐都有“选”或“不选”两种状态，n 个套餐共有 2^n 种组合。当 n = 30 时，组合数已经超过十亿，显然无法接受。

• 时间复杂度：O(2^n × n)
• 空间复杂度：O(n)
• 适用场景：数量极少且只需要一次性验证

方案二：DFS 加剪枝

深度优先搜索可以按套餐依次决策，并在价格超预算时剪枝。如果再配合前缀和、按性价比排序，能够解决一部分数据规模较小的问题。

但在最坏情况下，它仍然会退化成指数级搜索；而且递归状态中存在大量重复预算子问题。

方案三：二维动态规划

0-1 背包的核心是把问题拆成“前 i 个套餐、预算为 j”的子问题。

定义：

dp[i][j] = 只考虑前 i 个套餐，预算不超过 j 时的最大价值

对于第 i 个套餐，有两种决策：

1. 不选：价值继承 dp[i-1][j]；
2. 选：前提是 j >= cost[i-1]，价值为 dp[i-1][j-cost[i-1]] + value[i-1]。

因此转移方程为：

dp[i][j] = max(
    dp[i-1][j],
    dp[i-1][j-cost[i-1]] + value[i-1]
)

• 时间复杂度：O(n × budget)
• 空间复杂度：O(n × budget)

方案四：一维滚动数组

观察转移方程可以发现，计算第 i 行时，只依赖第 i-1 行，因此没有必要保存完整二维表。使用 滚动数组 后，空间复杂度可以从二维降为一维。

这也是本文重点讲解的写法。

实操步骤：用滚动数组求最大价值

第一步：定义一维状态

使用数组：

dp[j] = 当前已处理套餐中，预算不超过 j 时的最大价值

初始状态下，还没有处理任何套餐，因此无论预算是多少，最大价值都是 0。

第二步：按套餐逐个更新

对于每个套餐，都从大预算向小预算倒序遍历：

for price, score in zip(costs, values):
    for j in range(budget, price - 1, -1):
        dp[j] = max(dp[j], dp[j - price] + score)

其中：

• dp[j] 表示不买当前套餐；
• dp[j - price] + score 表示买当前套餐；
• range(budget, price - 1, -1) 保证只更新能买得起当前套餐的预算。

第三步：为什么必须倒序遍历

这是 0-1 背包最容易写错的地方。

在一维数组中，dp[j - price] 必须表示“尚未考虑当前套餐”的状态。倒序遍历时，j - price < j，而较小下标还没有被当前套餐更新，所以每个套餐最多使用一次。

如果写成正序遍历：

# 错误写法：可能重复购买同一个套餐
for j in range(price, budget + 1):
    dp[j] = max(dp[j], dp[j - price] + score)

当计算较大的 j 时，dp[j-price] 可能已经在本轮被当前套餐更新过，于是当前套餐会被重复选择。这对应的是完全背包，而不是 0-1 背包。

可运行 Python 代码

下面的代码不仅计算最大价值，还通过二维记录数组还原具体选择了哪些云主机套餐：

from typing import List, Tuple


def select_cloud_hosts(
    costs: List[int],
    values: List[int],
    budget: int
) -> Tuple[int, List[int]]:
    """
    在预算约束下选择云主机套餐。

    Args:
        costs: 每个套餐的价格，只能选择一次
        values: 每个套餐的业务价值
        budget: 最大预算

    Returns:
        最大价值以及被选择套餐的下标列表
    """
    n = len(costs)

    # dp[j]：预算不超过 j 时可获得的最大价值
    dp = [0] * (budget + 1)

    # chosen[i][j] 记录在考虑前 i 个套餐、预算为 j 时，是否选择第 i 个套餐
    chosen = [[False] * (budget + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        price = costs[i - 1]
        score = values[i - 1]

        # 0-1 背包必须倒序遍历，避免同一个套餐被重复选择
        for j in range(budget, price - 1, -1):
            buy = dp[j - price] + score
            if buy > dp[j]:
                dp[j] = buy
                chosen[i][j] = True

    # 从最终状态倒推具体方案
    selected = []
    remain = budget

    for i in range(n, 0, -1):
        if chosen[i][remain]:
            selected.append(i - 1)
            remain -= costs[i - 1]

    selected.reverse()
    return dp[budget], selected


if __name__ == "__main__":
    # 四款云主机套餐：价格与业务承载评分
    costs = [2000, 3000, 4000, 5000]
    values = [3, 4, 5, 6]
    budget = 10000

    max_value, selected = select_cloud_hosts(costs, values, budget)

    print("最大业务评分：", max_value)
    print("选择的套餐编号：", selected)
    print("总价格：", sum(costs[i] for i in selected))

输出结果：

最大业务评分： 13
选择的套餐编号： [0, 1, 3]
总价格： 10000

复杂度分析

假设套餐数量为 n，预算为 B：

• 时间复杂度：O(nB)，每个套餐最多遍历一次预算区间；
• 空间复杂度：
  • 只求最大价值时为 O(B)；
  • 上面代码为了还原选择方案，额外使用了 O(nB) 的记录数组。

如果只需要最大价值，保留一维 dp 即可；如果还需要输出具体组合，就必须保存额外的选择信息，或者使用二维 DP 表回溯。

状态转移的直观理解

以预算 10、套餐价格 [2,3,4,5] 为例，处理每个套餐时，本质是在回答同一个问题：

当前预算下，我要不要把这个套餐纳入方案？

如果不纳入，原方案不变；如果纳入，就要先给它预留价格，再把剩余预算能取得的最优价值加上当前套餐价值。

需要特别注意，dp[j] 的含义是“预算不超过 j”，而不是“必须恰好花完 j”。因此初始化全为 0 是合理的。如果题目要求恰好花完预算，通常需要把除 dp[0] 外的状态初始化为负无穷，表示不可达。

避坑总结：高频错误与修正方法

坑一：预算循环写成正序，导致物品重复选择

错误现象：单个高价值套餐可能被重复购买，答案异常偏大。例如价格为 2、价值为 3 的套餐，在预算 10 下可能被计算成选择多次。

修正方法：0-1 背包使用一维 滚动数组 时，预算必须从大到小遍历；完全背包才使用正序遍历。

坑二：错误初始化“恰好花费”状态

错误现象：题目要求不超过预算，却把 dp[1...budget] 初始化为负无穷，导致很多合法方案无法转移；或者题目要求恰好花完预算，却全部初始化为 0，把不可达状态当成合法状态。

修正方法：先判断题目语义。

• 不超过预算：dp = [0] * (budget + 1)；
• 恰好花费预算：dp[0] = 0，其余为 -inf。

坑三：只保存一维数组却试图还原方案

错误现象：使用滚动数组得到了正确最大价值，但无法知道具体选了哪些主机，因为旧状态已经被覆盖。

修正方法：如果要求输出组合，有两种常见方式：

1. 使用二维 dp 表，从 dp[n][budget] 回溯；
2. 保持一维价值数组，同时增加 chosen[i][j] 记录每次决策。

坑四：预算很大但没有评估伪多项式复杂度

错误现象：题目预算达到 10^9，即使套餐数量只有 100，创建长度为预算的数组也会直接内存溢出。

修正方法：O(nB) 是伪多项式复杂度，是否可用取决于预算数值规模。预算极大时，应考虑按价值维度 DP、Meet in the Middle，或结合题目约束使用搜索、贪心近似等方案。

结语

0-1 背包的套路可以概括为三句话：状态描述前若干物品在容量下的最优结果，转移时比较选与不选，一维滚动时容量倒序更新。掌握这套模型后，云主机选配、预算投放、资源限额等问题都能快速映射成统一的动态规划框架。

真正需要警惕的不是转移方程本身，而是遍历方向、状态语义、方案回溯和数据规模这四个工程细节。

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。