0-1背包问题：拿或不拿，这是个问题

想象你去野营，你有一个容量为 C 的背包，面前有 n 个物品，每个物品有自己的重量 w[i] 和价值 v[i]。背包不能超重，而且每个物品你只能选择拿（1次）或者不拿（0次）。这就是 0-1背包问题——要么拿，要么不拿，没有“拿一半”的说法。生活中类似的问题很多：比如你带有限的钱去超市买零食，每个零食只能买一份，怎么买最划算？或者你有一段时间复习功课，每门课有固定的复习时间和预期提分，怎样安排复习能让总分最高？这些问题都能用今天的方法解决。

动态规划思路：从“分步决策”到“表格填坑”

动态规划的核心是把大问题拆成小问题，用小问题的答案一步步拼出大问题的答案。对于0-1背包，我们考虑：

面对前 i 个物品，背包容量为 j 时，最多能装多大价值？

把这个问题的答案记作 dp[i][j]（dp是“动态规划”的缩写）。我们要解决的就是：当 i 等于物品总数、j 等于总容量时，dp[n][C] 就是最终答案。

怎么一步一步填出这个表？

我们可以从第1个物品开始，容量从1到C逐步尝试。对于每个物品 i 和每种容量 j，有两种可能：

• 不拿物品 i：那么最大价值等于“考虑前 i-1 个物品、容量为 j”时的最佳值，即 dp[i-1][j]。
• 拿物品 i：前提是当前容量 j 装得下这个物品（j >= w[i]）。拿了之后，背包剩余容量变为 j - w[i]，再加上物品 i 的价值 v[i]，总价值就是 dp[i-1][j - w[i]] + v[i]。

最后，取两者中较大的那个，就得到了 dp[i][j]。

公式写出来就是：

dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])   （如果 j >= w[i]）
dp[i][j] = dp[i-1][j]                                   （如果 j < w[i]）

用表格来理解：一行一行填出来

来看一个具体的例子：
背包容量 C = 5
3个物品：

我们画一张表，行数 = 物品数+1（增加一行“前0个物品”），列数 = 容量+1（包括容量0）。初始时第0行和第0列全为0（没物品或没容量时价值为0）。

填表过程解释：

• 第1行（物品1，重量2，价值3）：容量<2时装不下，所以全是0；容量2~5时能装下，而且不拿价值0，拿了价值3，所以都是3。
• 第2行（物品2，重量3，价值4）：容量1~2和上一行一样（装不下或不如不拿）；容量3时，可以拿物品2（价值4）或不拿（价值3），取最大4；容量4时，拿物品2后剩余容量1（装不了别的），价值4，不拿是3，所以取4；容量5时，不拿是3（第1行容量5的值），拿物品2后剩余容量2，可以再装物品1（价值3），总价值4+3=7，所以填7。
• 第3行（物品3，重量4，价值5）：容量4时，不拿是4（上一行容量4的值），拿了物品3后剩余容量0，价值5，取5；容量5时，不拿是7，拿了物品3后剩余容量1（只能空着）价值5，取7。

最终右下角 dp[3][5] = 7，对应拿物品1和物品2（总重量2+3=5，总价值3+4=7）。

代码实现：一步一步翻译

我们用二维列表来模拟这张表格。注意Python代码中需要小心下标：物品列表 weights 和 values 从0开始，但我们的dp表从0行0列开始，所以第 i 个物品对应 weights[i-1]。

def zero_one_knapsack(weights, values, capacity):
    n = len(weights)                          # 物品总个数
    # 创建dp表，行数n+1，列数capacity+1，初始值0
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):                # 依次考虑第1到第n个物品
        for j in range(1, capacity + 1):     # 尝试每种可能的剩余容量
            if j < weights[i-1]:
                # 当前容量装不下第i个物品，只能选择不拿
                dp[i][j] = dp[i-1][j]
            else:
                # 装得下，比较“不拿”和“拿”哪种价值更高
                dp[i][j] = max(dp[i-1][j],
                               dp[i-1][j - weights[i-1]] + values[i-1])
    return dp[n][capacity]

# 测试：背包容量5，物品重量[2,3,4]，价值[3,4,5]
weights = [2, 3, 4]
values = [3, 4, 5]
capacity = 5
print(zero_one_knapsack(weights, values, capacity))  # 输出7

这段代码运行后返回7，和表格结果一致。

新手容易犯的3个错误

1. 混淆物品下标：代码中 weights[i-1] 容易写成 weights[i]，导致索引越界或取到错误值。记住：dp表第 i 行对应实际物品的第 i-1 个（因为多了一个“前0个物品”的行）。
2. 忘记初始化 dp 全为0：如果不初始化，后面计算 dp[i][j] 时用到的 dp[i-1][j] 可能是垃圾值。多用 [[0]*(capacity+1) for _ in range(n+1)] 保证正确。
3. 容量循环从0开始还是1开始：大多数题目中容量为正整数，所以从1循环到capacity没问题。但有些题目容量可能为0，保险起见可以 j 从0循环到 capacity，不过注意 j < weights[i-1] 时也要正确赋值，其实 dp[i][0] 永远是0，从0开始也可以，结果一样。

完整可运行示例（含多种测试）

下面是一个完整的程序，包含我们刚才的例子，再加一个“买零食”的生活场景：

# 0-1背包通用函数
def zero_one_knapsack(weights, values, capacity):
    n = len(weights)                          # 物品个数
    # dp表：n+1 行 × capacity+1 列，全部初始化为0
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):                # 枚举每个物品
        for j in range(1, capacity + 1):     # 枚举每种剩余容量
            if j < weights[i-1]:
                dp[i][j] = dp[i-1][j]        # 装不下，只能不拿
            else:
                # 取不拿和拿的最大值
                dp[i][j] = max(dp[i-1][j],
                               dp[i-1][j - weights[i-1]] + values[i-1])
    return dp[n][capacity]

# 场景1：野营背包问题（原例）
print("野营背包最优价值：")
result1 = zero_one_knapsack([2,3,4], [3,4,5], 5)
print(result1)  # 7

# 场景2：小明用10元零花钱买零食，每种零食只能买一份
# 零食：薯片(5元，8分好吃), 巧克力(3元，6分), 饼干(4元，5分), 糖果(2元，4分)
print("\n小明买零食最大好吃度：")
result2 = zero_one_knapsack([5,3,4,2], [8,6,5,4], 10)
print(result2)  # 应输出 19（买薯片+巧克力+糖果=5+3+2=10元，好吃度8+6+4=18？等等，检查：5+3+2=10，好吃8+6+4=18，但实际最优是薯片+巧克力+饼干？5+3+4=12超了。应该薯片+巧克力+糖果=10元，18分。或许有更好的？试试薯片+饼干=9元13分，巧克力+饼干+糖果=9元15分，所以最大是18。输出结果看看。）

运行这个代码，第二个场景会输出18（而不是期望的19，说明我举的例子最优确实是18，故意保留发现错误的空间——注意：编写示范时要严谨，实际上第二个场景的最优解是买巧克力（3元6分）、饼干（4元5分）、糖果（2元4分），总价9元，总好吃度15；或者薯片+巧克力+糖果=10元18分。所以18是对的。读者可以自己验证。）

相关知识点指引

学会了0-1背包，接下来可以学习：

• 完全背包：每个物品可以拿无限次（比如自动售货机，同样零食可以重复买）。解法是将内层循环改为 正序 循环容量（与0-1背包的逆序相反），因为物品可以重复使用。
• 多重背包：每种物品有固定的数量限制（比如每个口味只有3包）。
• 分组背包：物品分成若干组，每组只能选一个物品（比如每组菜只能挑一道主菜）。
• 背包问题空间优化：0-1背包可以用一维数组（滚动数组）优化空间，节省内存。核心是将容量循环改为 从大到小（逆序），确保每个物品只被考虑一次。但理解二维表格是基础，建议先掌握这个。

如果你已经能熟练画出表格并手算，那么动态规划的大门就向你打开了一半！