动态规划2-0/1背包问题

type

Post

status

Published

date

Mar 2, 2026

slug

DynamicProgrammingBackpackproblem

summary

围绕0/1背包问题，对比集合法与表格法两种解法。集合法通过枚举每件物品拿或不拿的所有组合，剔除超重方案后选出最大价值，示例最优为A+B、价值35。表格法用dp[i][j]表示前i件物品在容量j下的最大价值，按“不拿”与“拿且装得下”两种情况取最大值，避免重复计算，是标准动态规划解法。

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

这是最符合人类直觉的方法，核心思想是把所有可能的组合列出来，然后找给定容量里价值最大那个。这就好比对于每个物品做一个选择——拿/不拿。

因此我们列出所有的这种集合：

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

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

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

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

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

{A, C} -> 重量5 。

{B, C} -> 重量7 。

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

分析以上组合我们可以排除重量超过4公斤的组合，然后挑出价值最高的组合第5组{A, B}，价值 35 元。

🌟

总结

优点：思路简单，像列举法。

缺点：物品一多就“爆炸”。每多一件物品，组合数就翻一倍。10件物品就有1024种组合，100件物品的话，全宇宙的计算机算到宇宙灭亡都算不完。

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

🌟

我们不再考虑具体的物品组合，而是通过一系列更小的问题，去把答案记在一张表格里，然后去高效的解决更复杂的问题。

这是动态规划的经典解法之一，核心是“记笔记”和“用之前的答案推新答案”，避免重复计算。

还是那个例子，我们设计一个表格记录答案来解决问题。

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

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

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

我们开始填表，规则只有一条：

面对第i件物品，在容量j下，我们只需要考虑：

概括来说就是，对于dp[i][j]：

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

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

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

开始填：

初始化，此时i=0,j=0。

代表：”一件物品都不考虑“，可想而知此时任何容量下价值都为0。

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

i=1,即只考虑物品A

j=0(容量0)——装不下A，价值为0。
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	ㅤ	ㅤ	ㅤ	ㅤ	ㅤ

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	ㅤ	ㅤ	ㅤ	ㅤ	ㅤ

i=3,即考虑物品A和B以及C(A+B+C容量为8)。

由上面可知，我们背包容量合计为4，装不下C，故dp值不变

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

🌟

表格法总结：

优点：效率极高！我们只进行了 (物品数 × 容量) 次计算。100件物品，容量1000，也只需计算10万次。

缺点：思路不那么直观，需要理解“状态”和“转移”的概念。

精髓：表格的右下角 dp[3][4]就是全局最优解。这个35，并不是凭空算的，而是由前面更小、更简单的问题答案（15，20等）像搭积木一样组合出来的，并且每个答案只计算一次。

最后

两种方法的灵魂对比：

假设你要解决“用前3件物品装满4kg背包”这个大问题 (dp[3][4])：

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

表格法：

一句话总结：

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

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

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

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

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

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