0-1背包的重叠子问题

来源：9-5 0-1背包问题

wxz123

2019-11-26

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

写回答

1回答

liuyubobobo

2019-11-27

随便拿 PPT 中的一张图：

//img.mukewang.com/szimg/5ddd8e6f09f5f05818981068.jpg

要想求解 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 背包问题的状态转移方程：

//img.mukewang.com/szimg/5ddd8f5409ca3e2e18941054.jpg

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

继续加油！：）

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7410 学习 · 1150 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1