主要记录下背包问题的入门 0-1 背包问题

1. 背包问题

想象你是个探险家，有一个背包，背包最多能装 W 重量的东西。
现在有 n 件物品，每件物品有：

• 重量 w[i]
• 价值 v[i]

目标：在不超过背包容量的前提下，选择物品使总价值最大。

2. 0-1 背包问题

0-1 背包的含义是——每件物品要么不选（0 次），要么选一次（1 次）。
不能分割物品，也不能重复选取。

例子：

1
2
3
4

物品:  1   2   3
重量:  2   1   3
价值:  4   2   3
容量: 4

问题：怎么选才能让总价值最大？

3. 动态规划思想

动态规划的核心思路是分阶段做决策，记录每一步的最优结果，避免重复计算。

为了让计算过程更直观，我们先定义一个二维表：
dp[i][j] = 在只考虑前 i 个物品的情况下，当背包容量为 j 时，能得到的最大价值。

这样，我们最终要找的答案就是 dp[n][W]。

4 初始化

在开始推算 dp[i][j] 之前，我们需要先明确边界条件，也就是最简单的情况。

没有物品时
你什么都不能装，所以价值一定是 0：
dp[0][*] = 0

背包容量为 0 时
无论有多少物品，你都装不进去任何东西，所以价值也一定是 0：
dp[*][0] = 0

这样初始化之后，就相当于给了动态规划一张起始地图，后面的每一步都能在这张地图上找到参考点。
从这些基础值出发，我们才能一步步推算出更复杂的情况。

5 决策过程

前面边界条件确定之后，我们开始往后考虑，我们在考虑第 i 个物品时，有两个选择：

不选它

那么背包的最大价值就是不选它时的结果：
dp[i][j] = dp[i-1][j]

选它

如果背包容量 j ≥ w[i]，那么我们可以把它放进背包。
这样背包的容量会减少 w[i]，同时获得它的价值 v[i]：
dp[i][j] = dp[i-1][j-w[i]] + v[i]

状态转移方程（核心公式）

把两种选择放在一起取最大值，就是：

1
2
3
4

dp[i][j] = max(
    dp[i-1][j],                     # 不选第 i 个物品
    dp[i-1][j-w[i]] + v[i]          # 选第 i 个物品
)

前提条件：j >= w[i]。

想象你一个个地看物品，手上拿着背包，每次都问自己：

“我拿这个物品好，还是不拿它好？”
“拿了它，能让我背包的价值更高吗？”

6 代码实现（Python）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, W + 1):
            if j >= weights[i-1]:
                dp[i][j] = max(dp[i-1][j],
                               dp[i-1][j-weights[i-1]] + values[i-1])
            else:
                dp[i][j] = dp[i-1][j]
    return dp[n][W]

weights = [2, 1, 3]
values = [4, 2, 3]
W = 4
print(knapsack(weights, values, W))  # 输出: 6

这个例子中选物品 1(2kg,4$) 和物品 2(1kg,2$) 得到最大价值 6。