01 背包问题可不可以不用动态规划解？

[hakunamatata11]

爆搜法和贪心法也是解决 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 背包] + 试听报名截图即可免费获得整套课程。

参与条件：

九章新用户（未在九章购买过课程的都算新用户哦~）