完全背包问题－含优化

2019-11-06 06:06:27

字体：大中小

来源：转载

供稿：网友

**题目**有N件物品和一个容量为V的背包，每件物品可无限次使用。第i件物品的所需容量是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

由于物品可以无限次使用，商品ｉ以及商品ｊ，如果ｃ[i]<=c[j] and w[i]>=w[j]，那么如果要达到最大价值，无论如何都不必装入物品ｊ。商品优化代码如下：

#coding=utf-8class Solution(): def full_package(self,goods,max_V): self.goods_remove(goods) PRint goods def goods_remove(self,goods): # 操作简化，将所有的不符合条件的good删除 good_delete = set([]) #方便查找，商品不必重复删除 for i in range(len(goods)): #如果商品已经在删除列表，那么没必要再考虑比这个商品ｊ还差劲的商品ｋ，因为商品列表中一定存在ｉ优于ｊ，才导致ｊ出现在删除列表，商品ｋ如果差于商品ｊ，那么商品ｋ一定差于商品ｉ，即ｉ优于ｋ，ｋ肯定也在删除列表。。。 if i in good_delete:continue for j in range(len(goods)): if goods[i][0] <= goods[j][0] and goods[i][1] >= goods[j][1]: if j == i: continue good_delete.add(j) elif goods[i][0] >= goods[j][0] and goods[i][1] <= goods[j][1]: if j == i: continue good_delete.add(i) else:continue good_delete = list(good_delete) good_delete.sort(reverse=True) for i in good_delete: del goods[i]

完全背包问题有２种解法解法１：采用０１背包问题的相关思路，将所有物品的c[i]*2^k<=V,加入到goods中，因为c[i]*2^k组合可以满足调用物品i的任意一种情况，相当于数字２进制表示。然后后续采用０１背包问题完全一致的解法即可，解法１代码如下：

#coding=utf-8class Solution(): def full_package(self,goods,max_V): self.goods_remove(goods) goods_add = [] for i in goods: k = 1 while i[0]*(2**k)<=max_V: goods_add.append([i[0]*(2**k),i[1]*(2**k)]) k+=1 goods.extend(goods_add) f = [0] * (max_V + 1) for i in range(len(goods)): for v in xrange(max_V,goods[i][0]-1,-1): #特别注意这个ｉｆ语句，如果不写，结果可能会出现错误！！！ if v>=goods[i][0]: f[v] = max(f[v],f[v-goods[i][0]]+goods[i][1]) print f return f[max_V] def goods_remove(self,goods): # 操作简化，将所有的不符合条件的good删除 good_delete = set([]) for i in range(len(goods)): if i in good_delete: continue for j in range(len(goods)): if goods[i][0] <= goods[j][0] and goods[i][1] >= goods[j][1]: if j == i: continue good_delete.add(j) elif goods[i][0] >= goods[j][0] and goods[i][1] <= goods[j][1]: if j == i: continue good_delete.add(i) else:continue good_delete = list(good_delete) good_delete.sort(reverse=True) for i in good_delete: del goods[i]goods = [[5,12],[4,3],[7,10],[2,3],[6,6]]test = Solution()print test.full_package(goods,16)

结果如下所示: [0, 0, 3, 3, 6, 12, 12, 15, 15, 18, 24, 24, 27, 27, 30, 36, 36] 36

解法２：由于每个物品可以使用无限次，求解０１背包问题时，value需要逆序计算，正式为了保证每件物品只可以选择１次，无法无限次选用。正是由于物品可以使用无限次，完全背包问题其实只要对value顺序进行计算，求出结果即可。代码如下：

#coding=utf-8class Solution(): def full_package(self,goods,max_V): self.goods_remove(goods) f = [0] * (max_V + 1) for i in range(len(goods)): for v in range(max_V+1): #特别注意这个ｉｆ语句，如果不写，结果可能会出现错误！！！ if v>=goods[i][0]: f[v] = max(f[v],f[v-goods[i][0]]+goods[i][1]) print f return f[max_V] def goods_remove(self,goods): # 操作简化，将所有的不符合条件的good删除 good_delete = set([]) for i in range(len(goods)): if i in good_delete: continue for j in range(len(goods)): if goods[i][0] <= goods[j][0] and goods[i][1] >= goods[j][1]: if j == i: continue good_delete.add(j) elif goods[i][0] >= goods[j][0] and goods[i][1] <= goods[j][1]: if j == i: continue good_delete.add(i) else: continue good_delete = list(good_delete) good_delete.sort(reverse=True) for i in good_delete: del goods[i]goods = [[5,12],[4,3],[7,10],[2,3],[6,6]]test = Solution()print test.full_package(goods,16)

结果如下所示： [0, 0, 3, 3, 6, 12, 12, 15, 15, 18, 24, 24, 27, 27, 30, 36, 36] 36

上一篇：maven配置阿里云镜像

下一篇：【JZOJ3296】【SDOI2013】刺客信条(assassin)