爆搜法和贪心法也是解决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种的变形以及组合。
如果你想把这个知识点学得更透彻，可以听一听《背包四讲》，基础知识和刷题都覆盖到了~
转载：https://blog.csdn.net/JiuZhang_ninechapter/article/details/104075003
查看评论