由于物品可以無限次使用，商品ｉ以及商品ｊ，如果ｃ[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
新聞熱點
疑難解答
