完全背包问题-含优化

3/8/2017来源:ASP.NET技巧人气:1059

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

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

#coding=utf-8 class 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)): #如果商品已经在删除列表,那么没必要再考虑比这个商品j还差劲的商品k,因为商品列表中一定存在i优于j,才导致j出现在删除列表,商品k如果差于商品j,那么商品k一定差于商品i,即i优于k,k肯定也在删除列表。。。 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]

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

#coding=utf-8 class 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语句,如果不写,结果可能会出现错误!!! 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


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

#coding=utf-8 class 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语句,如果不写,结果可能会出现错误!!! 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