0-1背包问题

来源：9-3 发现重叠子问题 Integer Break

pfco

2019-05-24

老师，我看到这个问题想清楚了它的最优子结构的特性，但是重叠子问题我一直想不明白在哪里，因为对于一个物品的话，只有两种情况，一种是放入背包，另一种是不放入背包，那么对于下一个物体，它所对应的背包此时的容量也是不同的，这样递归下去，应该没有重复计算的元组呀？

写回答

1回答

liuyubobobo

2019-05-24

已采纳

我不确定你看了这个课程后续的内容。这个课程仔细讲解了背包问题。下面的回答基于这个课程的代码。

其实只要你写出一个问题的递归函数，就定义出了重叠子问题。

比如我们的背包问题代码：

// 用 [0...index]的物品,填充容积为c的背包的最大价值    
int bestValue(const vector<int> &w, const vector<int> &v, int index, int c)

这个函数定义，就是重叠子问题。我们会不断求：用 [0...index]的物品,填充容积为c的背包的最大价值。

如果你不认为有重复，可以在我们记忆化搜索中，把记忆化的部分扔掉，看看是不是对于大规模的数据，运行时间就更长了？但是加入了记忆化搜索，时间就短了？这个省去的时间，就是重复搜索的时间：）

继续加油！：）

pfco

liuyubobobo

明白了，老师，我其实考虑的就是这个，谢谢老师的答复

2019-05-24

共4条回复

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

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

7410 学习 · 1150 问题

相似问题

回答 1

回答 1

回答 1

回答 2

回答 2