• 你有一个背包，容量最大为 4 公斤。

物品	重量(kg)	价值(元)
A	1	15
B	3	20
C	4	30

面前有几件物品，每件只能拿（1）或不拿（0）——这就是“01”的含义。目标是如何装包，让总价值最高。

方法一：集合法（暴力搜索 / 回溯法）

1. {}———此时为空包，价值和重量为0。

2. {A}———重量1，价值15。

3. {B}———重量3，价值20。

4. {C}———重量4，价值30。

5. {A,B}———重量4，价值35。

6. {A, C} -> 重量5 。

7. {B, C} -> 重量7 。

8. {A, B, C} -> 重量8 。

方法二：表格法（动态规划标准解法）

• row(i)——代表“只考虑前i件物品”。比如说i=2，此时我们只考虑物品A和B。

• column(j)——代表”背包当前的容量“。从 0 到 4（我们的背包总容量）。

• 单元格dp[i][j]的值——代表的是在”只考虑前i件商品，背包当前容量为j“的条件下，我们能获得的最大价值。

• 不拿这件物品的话，那么价值就等于”没考虑它时，同等容量下的最大价值“，即dp[i-1][j]。

• 拿这件物品的话（前提是背包装得下），那么价值就等于”这件物品的价值“+”没选择它时，剩余容量下的背包最大价值“，即物品价值 + dp[i-1][j-物品重量]。

• 我们永远选择两者中价值更大的那个。max(不拿的价值， 拿的价值)

1. 初始化，此时i=0,j=0。
1. 代表：”一件物品都不考虑“，可想而知此时任何容量下价值都为0。

ㅤ	0	1	2	3	4
0	0	0	0	0	0
1	ㅤ	ㅤ	ㅤ	ㅤ	ㅤ
2	ㅤ	ㅤ	ㅤ	ㅤ	ㅤ
3	ㅤ	ㅤ	ㅤ	ㅤ	ㅤ

2. i=1,即只考虑物品A
1. j=0(容量0)——装不下A，价值为0。
2. j=1,2,3,4——都能装下A，价值都是15。

ㅤ	0	1	2	3	4
0	0	0	0	0	0
1	0	15	15	15	15
2	ㅤ	ㅤ	ㅤ	ㅤ	ㅤ
3	ㅤ	ㅤ	ㅤ	ㅤ	ㅤ

3. i=2,即考虑物品A和B(A+B容量为4)，即前2件商品———关键。
我们看 dp[2][4](考虑A和B，容量为4)：
• 不拿B：价值等于 dp[1][4] = 15。
• 拿B：B价值20 + dp[1][4-3]= 20 + dp[1][1]= 20 + 15 = 35。
• max(15, 35) = 35。我们就在这里找到了最优解！
同理我们看dp[2][2] :
• 不拿B:价值等于 dp[1][2] = 15。
• 拿B：B价值等于20 + dp[1][2-3]= 20 + dp[1][-1]。背包容量不够，dp值不变。
同理我们看dp[2][3] :
• 不拿B:价值等于 dp[1][3] = 15。
• 拿B：B价值等于20 + dp[1][3-3]= 20 + dp[1][0]=20。

ㅤ	0	1	2	3	4
0	0	0	0	0	0
1	0	15	15	15	15
2	0	15	15	20	35
3	ㅤ	ㅤ	ㅤ	ㅤ	ㅤ

4. i=3,即考虑物品A和B以及C(A+B+C容量为8)。
由上面可知，我们背包容量合计为4，装不下C，故dp值不变

ㅤ	0	1	2	3	4
0	0	0	0	0	0
1	0	15	15	15	15
2	0	15	15	20	35
3	0	15	15	20	35

最后

• 集合法：直接冲进仓库，面对3件物品开始疯狂尝试各种排列组合。

• 表格法：
1. 先问：“如果只有1件物品，在容量1/2/3/4下怎么办？” 把答案写在本子(dp表)第一行。
2. 再问：“在有前1件物品答案的基础上，加入第2件物品会怎样？” 利用第一行的答案，算出第二行的答案。
3. 最后问：“在有前2件物品答案的基础上，加入第3件物品会怎样？” 利用第二行的答案，轻松算出最终答案。

• 集合法是 “是什么？” —— 直接寻找那个正确的集合。

• 表格法是 “如何从更简单的情况变过来？” —— 通过记录和推导所有小问题的答案，来构建大问题的答案。这就是动态规划的智慧。