0-1背包问题

Question

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

Answer 1

liuyubobobo 2019-05-24 12:33:25

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

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

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

https://github.com/liuyubobobo/Play-with-Algorithm-Interview/blob/master/09-Dynamic-Programming/Course%20Code%20(C%2B%2B)/05-0-1-knapsack/main.cpp

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

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

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

继续加油！：）

• 提问者 pfco #1

  非常感谢！

• 提问者 pfco #2

  嗯嗯，我明白老师的意思，但是我的意思是c对于有些情况并没有重复，也就是在考虑[0,index]这一层的最大的收益时，c可能会一直不相同，这时候的记忆化搜索与递归的调用函数的次数是一样的，老师这里你说每一次考虑的都是用[0,index]的物品，填充背包容量为c的最大价值，是不是可以理解为一些情况，例如[2,2,2,5],背包容量为6，它的部分解空间树为
                                        [4,6]（前半部分为index，后半部分为背包容量）
                                        /   \
                                     [3,6]  [3,4]
                                     / \     /  \
                                [2,6]  [2,4][2,4][2,2]
  它的里面就会包含很多重复的计算，还有我觉得如果不是我列举的这一类情况，递归问题的重复计算的主要是对于[-1,c]这种情况的重复的计算太多了，也就是背包容量为c，但是什么也不放，这时的收益就为0

• liuyubobobo 回复 提问者 pfco #3

  c可能会一直不相同，但也可能有很多相同：）一旦有很多相同，就会恶化为指数级别的算法。

点开查看后面1条评论