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

来源:9-6 0-1背包问题的优化和变种

wxz123

2019-11-27

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)数据对,我想问的是,对于这种递归解法,重叠子问题体现在哪里呢

写回答

1回答

liuyubobobo

2019-11-27

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


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


继续加油!:) 

0
0

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

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

7410 学习 · 1150 问题

查看课程