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 个物品,看看有没有效果?
继续加油!:)
00
相似问题