0-1背包的重叠子问题2

Question

class Bag01:
    def knapsack01(self,w,v,C):
        n=len(w)
        return self.bestvalue(w,v,n-1,C)

    def bestvalue(self,w,v,index,c):
        if index<0 or c<=0:
            return 0
        print(index,c)
        res=self.bestvalue(w,v,index-1,c)
        if c>=w[index]:
            res=max(res,v[index]+self.bestvalue(w,v,index-1,c-w[index]))
        return res
w=[1,2,3]
v=[6,10,12]
a=Bag01()
print(a.knapsack01(w,v,5))

老师您看一下我这个代码，用动态规划的方法解释重叠子问题我理解，但是用普通的递归法，我将您举的例子的递归过程打印了一下，并没有发现重复的（index，c）数据对，我想问的是，对于这种递归解法，重叠子问题体现在哪里呢

Answer 1

liuyubobobo 2019-11-27 13:38:50

我没有看你的代码，但是你的数据量太小了。

0-1背包问题的 dp 空间大小是 物品个数 * 背包重量。按照你的例子，就是 3 * 5 = 15 个空间。但你的数据量总共只有 3 个，排列组合一下才 8 种可能，都填不满 15 个空间。增大数据量试试看，随机生成 20 个物品，看看有没有效果？

继续加油！：）