爆搜法和贪心法也是解决 01 背包的思路，但都存在局限。
爆搜法解 01 背包
举例：背包容量 m = 10，物品大小 A = [2, 3, 5, 7] ，物品价值 V = [1, 5, 2, 4]
爆搜解法：分别枚举每一个物体取或者不取，1 代表取，0 代表不取
爆搜算法的局限：
贪心法解 01 背包
取价值最高：
- m=2, A = [1, 1, 2], V = [2, 2, 3]
- 贪心答案：3，正确答案：4
取重量最轻 ：
- m=2, A = [1, 1, 2], V = [1, 1, 3]
- 贪心答案：2，正确答案：3
取单位价值最高：
- m=3, A = [1, 1, 3], V = [2, 2, 5]
- 贪心答案：4，正确答案：5
可以看到，所有的贪心都是错误的！！！
那么，动态规划如何解 01 背包呢？
举例 1：
背包容量 m = 10，物品大小 A = [2, 3, 5, 7] ，物品价值 V = [1, 5, 2, 4]。
使用数组来记录取前 i 个物品，在容量 j 的情况下能取的最大价值 ：
dp[i][j]表示前 i 个物体，在容量 j 的情况下，能取到的最大价值
如果取第 i 个物体，价值为 dp[i - 1][j - A[i]] + V[i] (j-A[i]>0)
如果不取第 i 个物体，价值为 dp[i - 1][j]
状态转移：dp[i][j] = max(dp[i - 1][j – A[i]] + V[i], dp[i - 1][j])
实际上，除了 01 背包外，我们还需要掌握背包问题的另外 2 种的子问题——完全背包和多重背包问题，剩下一些都是这 3 种的变形以及组合。
如果你想把这个知识点学得更透彻，可以听一听《背包四讲》，基础知识和刷题都覆盖到了~
这门原价$199 的课程，现在免费！
参与方式：
戳我免费试听后，添加九章 Sunny 微信 jiuzhang15，回复 [ V2EX 背包] + 试听报名截图即可免费获得整套课程。
参与条件：
九章新用户（未在九章购买过课程的都算新用户哦~）
Select Language