挑挑拣拣，价值最高——0-1背包问题

周末去郊游，你的背包只能装10公斤的物品。你有几样宝贝：一个水壶（3公斤，值10元）、一块面包（1公斤，值5元）、一个帐篷（5公斤，值20元）、一个相机（2公斤，值15元）、一本书（4公斤，值8元）。怎样装能让总价值最高？每个物品要么装进背包（1），要么不装（0），不能只装一半。这就是0-1背包问题。

在编程中，背包问题是一类经典的“选择最优组合”问题。0-1背包是它最基础的形式，学会了它，你就能解决很多生活中的选择难题，比如假期旅行带哪些零食、买游戏装备时如何分配有限的零花钱。

1. 问题拆解：从“不拿”和“拿”开始

假设我们有一个容量为 C 的背包，有 n 个物品，每个物品有自己的重量 w_i 和价值 v_i。我们要从中选一些物品（每个最多选一次），使总重量不超过 C，且总价值最大。

怎么思考呢？可以这样想：对每一个物品，我们只有两种选择——不拿或拿（拿的前提是装得下）。如果我们能知道“不考虑这个物品时的最优解”和“考虑这个物品后的可能最优解”，就能一步一步推出最终答案。

动态规划（Dynamic Programming，简称DP）就是用来记录这些“中间结果”的。我们用一个二维数组 dp[i][j] 来表示：从第1个到第i个物品中选，总重量不超过 j 时，能获得的最大价值。

用生活中的例子：假设你已经看了前3个物品（水壶、面包、帐篷），背包容量为5公斤，你会怎么组合？这个结果就可以存在 dp[3][5] 里。接着看第4个物品（相机），你可以在 dp[3][5] 的基础上决定要不要加上它。

2. 动态规划思路——手把手教你填表

我们用二维数组 dp，大小为 (n+1) × (C+1)，初始全部为0。其中 n 是物品个数，C 是背包容量。dp[i][j] 中的 i 从0到 n，j 从0到 C。i=0 表示没有物品，所以价值全是0。

现在一个物品一个物品地考虑：

不拿第 i 个物品：那么前 i 个物品的最大价值就等于前 i-1 个物品的最大价值，即 dp[i][j] = dp[i-1][j]。
拿第 i 个物品（前提是当前剩余容量 j 至少能装下这个物品的重量 w_i）：那么价值就是“前 i-1 个物品在容量为 j - w_i 时的最大价值”加上这个物品的价值，即 dp[i][j] = dp[i-1][j - w_i] + v_i。

我们取两种选择中较大的那个，就得到了 dp[i][j]。

手动填表试一试

还是用郊游例子：物品列表（重量, 价值）：

物品1：水壶 (3, 10)
物品2：面包 (1, 5)
物品3：帐篷 (5, 20)
物品4：相机 (2, 15)
物品5：书 (4, 8)

背包容量 C=10。

先画出表格，行 i 从0到5，列 j 从0到10。初始全0。
下面只演示关键几步：

i=1（考虑水壶）：
j从0到2，容量<3，不能拿，dp[1][j]=0；
j=3时，可以拿，dp[1][3] = max(0, dp[0][0]+10)=10；
j=4..10时，同样可以拿，dp[1][j]=10（因为只有这一个物品）。
i=2（加入面包）：
对每个j，比较不拿面包（dp[1][j]）和拿面包（dp[1][j-1]+5）。
例如j=1：不拿=0，拿=dp[1][0]+5=5，取5 → dp[2][1]=5
j=2：不拿=0，拿=dp[1][1]+5=5，取5
j=3：不拿=10，拿=dp[1][2]+5=5，取10
j=4：不拿=10，拿=dp[1][3]+5=10+5=15，取15
继续填下去，最终右下角 dp[5][10] 就是答案。

3. 代码实现（二维数组版本）

下面是完整的Python代码，每行变量都加了中文注释，方便你理解。

def knapsack_01(weights, values, capacity):
    # weights: 每个物品的重量列表
    # values:  每个物品的价值列表
    # capacity: 背包的总容量
    n = len(weights)                     # 物品个数
    
    # 创建二维列表，大小为 (n+1) x (capacity+1)，全部初始化为0
    # dp[i][j] 表示从前i个物品中选，总重量不超过j的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    # 从第1个物品开始遍历，i从1到n
    for i in range(1, n + 1):
        w = weights[i-1]                 # 当前物品的重量（注意下标要减1）
        v = values[i-1]                  # 当前物品的价值
        # 遍历所有可能的背包容量 j，从1到capacity
        for j in range(1, capacity + 1):
            if j < w:
                # 如果当前背包容量装不下这个物品，只能不拿
                dp[i][j] = dp[i-1][j]
            else:
                # 装得下，比较“不拿”和“拿”哪个价值更大
                # 不拿：dp[i-1][j]
                # 拿：dp[i-1][j - w] + v
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - w] + v)
    
    # 最终答案存储在 dp[n][capacity] 中
    return dp[n][capacity]

# 测试：郊游的例子
weights = [3, 1, 5, 2, 4]       # 每个物品的重量（公斤）
values  = [10, 5, 20, 15, 8]    # 每个物品的价值（元）
capacity = 10                    # 背包容量（公斤）

best_value = knapsack_01(weights, values, capacity)
print("最大总价值:", best_value)   # 输出：最大总价值: 45

运行结果：45。对应的是拿水壶（3kg,10元）、帐篷（5kg,20元）、相机（2kg,15元），总重量3+5+2=10kg，总价值10+20+15=45元。

4. 新手容易犯的错误

忘记初始化 dp 数组为0：如果不初始化，Python中列表可能是任意值，导致结果出错。所以一定要用 [0] * (capacity+1) 等方式初始化。
下标混乱：代码中物品的索引从0开始，但 dp[i] 中的 i 从1开始对应第i个物品。所以取重量和价值时要用 weights[i-1] 和 values[i-1]。很多新手忘记减1，导致访问错误。
容量循环范围写错：j 应该从1到 capacity（包含），不能写成 range(capacity)（那会漏掉容量为0的情况，但容量0本来就没用，不过最好保持一致）。实际上容量0不需要考虑，因为任何物品重量>0，所以 dp[i][0]=0。但注意 j 至少要从1开始，确保 j-w 非负。
状态转移方程写反：有些同学会写成 dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v)，注意第二个应该是 dp[i-1][j-w]，不能写成 dp[i][j-w]。因为当前物品只能拿一次，如果用了 dp[i][j-w]，就相当于允许重复拿同一个物品（那叫完全背包问题）。

5. 完整可运行示例（含测试多种情况）

你可以把下面的代码复制到 Python 环境中运行，看看不同数据的结果。

def knapsack_01(weights, values, capacity):
    # weights: 每个物品的重量列表
    # values:  每个物品的价值列表
    # capacity: 背包的总容量
    n = len(weights)                     # 物品个数
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]  # 初始化dp表

    for i in range(1, n + 1):
        w = weights[i-1]                 # 当前物品重量
        v = values[i-1]                  # 当前物品价值
        for j in range(1, capacity + 1):
            if j < w:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - w] + v)
    return dp[n][capacity]

# ---------- 测试1：郊游例子 ----------
weights1 = [3, 1, 5, 2, 4]
values1  = [10, 5, 20, 15, 8]
cap1 = 10
print("郊游最优价值:", knapsack_01(weights1, values1, cap1))  # 45

# ---------- 测试2：零花钱买游戏装备 ----------
# 你有50元零花钱，想买以下游戏道具：
# 剑：重量20元，价值100点
# 盾：重量15元，价值80点
# 药水：重量10元，价值60点
# 弓箭：重量25元，价值120点
weights2 = [20, 15, 10, 25]      # 相当于价格（重量）
values2  = [100, 80, 60, 120]    # 游戏实力值（价值）
cap2 = 50
print("游戏装备最优价值:", knapsack_01(weights2, values2, cap2))  # 应该拿剑+盾+药水=20+15+10=45，价值100+80+60=240；或者剑+弓箭=45，价值220，所以最优240

# ---------- 测试3：只有一个物品 ----------
weights3 = [7]
values3  = [9]
cap3 = 5
print("装不下时:", knapsack_01(weights3, values3, cap3))  # 0，因为背包容量小于物品重量

运行后你会看到输出：

郊游最优价值: 45
游戏装备最优价值: 240
装不下时: 0

6. 相关指引——接下来学什么？

0-1背包是背包问题的“大哥大”，它的思想还能延伸到：

完全背包问题：每个物品可以拿无限次（比如游戏中的金币，你想拿多少个都行，只要背包够大）。
多重背包问题：每个物品有数量限制（比如水壶最多带2个）。
分组背包问题：物品分成几组，每组只能选一个（比如零食组、饮料组、玩具组，每组只能挑一样）。
二维费用背包：不仅考虑重量，还考虑体积（比如背包同时限制重量和体积）。

掌握0-1背包，你就拿到了通往动态规划世界的钥匙。以后遇到“选择最优子集”的问题，都可以试试用动态规划来解决。

Python背包问题（0-1背包）