0-1背包的重叠子问题

Question

老师 0-1背包使用递归时的重叠子问题体现在什么地方呢？我自己举了几个例子并没有发现重叠子问题在什么地方出现。。。

Answer 1

liuyubobobo 2019-11-27 04:47:47

随便拿 PPT 中的一张图：

要想求解 F(2, 4)，即使用 0，1，2 三个可选物品，填满容量为 4 的背包，

我们只需要看 F(1, 4)，即只是用 0，1 两个可选物品，填满容量为 4 的背包；

或者 F(1, 1) + v[2]，即使用 0，1 两个可选物品，填满容量为 1 的背包，在这个基础上加上 2 号物品的价值，

这两者，取最大值就好了。

也就是为了求解 F(2,4)，我们需要求解 F(1,4) 和 F(1, 1)。

F(1, 4) 和 F(1, 1) 就是重叠子问题，我们之前已经求过了，我们不需要再求了。

根据上面的解释，再仔细理解一下我们这一小节介绍的 0-1 背包问题的状态转移方程：

 

建议再重新看一遍这一小节，再理解一下？

继续加油！：）