顯示揹包python遞歸的最大值和項目

Question

我們需要返回項目的最大值以及組成該最大值的項目。

列表輸入格式爲[[weight1, value1], [weight2, value2]]。

用下面的代碼，我只返回最大值。

請問有人可以幫我把這個價值與物品一起退回嗎？

def knapsack(capacity, itemList): 
    """ 
    Returns the maximum value and the list of items to keep. 
    """ 
    if len(itemList) == 0: 
     return 0 
    elif itemList[-1][0] > capacity: 
     return knapsack(capacity, itemList[:-1]) 
    else: 
     return max(
      knapsack(capacity, itemList[:-1]), 
      knapsack(capacity-itemList[-1][0], itemList[:-1]) + itemList[-1][1]) 

print (knapsack(6, [[1, 4], [5, 150], [4, 180]])) 
# should return [184, [[1, 4], [4, 180]]] 
# returns 184 

Answer 1

我覺得一個元組實際上會更有意義，因爲你大概不會修改這個值。您可以首先注意到，如果您已經擁有這些項目，實際上不需要返回該值，因爲您可以在之後將它們相加。一種方法是使用額外的參數。 我只給你基本情況:)

def knapsack(capacity, itemList, taken): 
    """ 
    Returns the maximum value and the list of items to keep. 
    """ 
    if len(itemList) == 0: 
     return (0,taken) 
    elif itemList[-1][0] > capacity: 
     return (knapsack(capacity, itemList[:-1]), taken) 
    else: 
     #you will need to compute the values first, save them, and then update the taken variable as needed depending on the max 
     return max(
      knapsack(capacity, itemList[:-1]), 
      knapsack(capacity-itemList[-1][0], itemList[:-1]) + itemList[-1][1]) 

print (knapsack(6, [[1, 4], [5, 150], [4, 180]])) 
# should return [184, [[1, 4], [4, 180]]] 
# returns 184 

Answer 2

我會通過存儲解決方案，以遞歸沿途子調用做到這一點。您的解決方案基本上說，解決揹包問題有N項和電容C的最大：

Soln(N,C) = max (Soln(N-1,C), Soln(N-1, C-W_n) + Vc) 

所以，如果我們存儲在字典解決這些子問題（一個數組也可使用），您可以使用相同的邏輯向後工作。看看N，C問題的解決方案是否等於N-1，C問題。如果是這樣，N項不在麻袋中，否則是。

d = {} #maps from (itemCount, capacity) to best Value 
# (also useful for when/if you convert to dp/memoized version) 
def knapsack(capacity, itemList): 
    """ 
    Returns the maximum value and the list of items to keep. 
    """ 
    if len(itemList) == 0: 
     return 0 
    elif itemList[-1][0] > capacity: 
     ans = knapsack(capacity, itemList[:-1]) 
     d[(len(itemList), capacity)] = ans 
     return ans 
    else: 
     ans = max(knapsack(capacity, itemList[:-1]), knapsack(capacity-itemList[-1][0], itemList[:-1]) + itemList[-1][1]) 
     d[(len(itemList), capacity)] = ans 
     return ans 

items = [[5, 150], [1, 4], [4, 180]] 
startCap = 6 
print knapsack(startCap, items) 


#Work Backwards 
itemNo = 3 
startCap = 6 
curValue = d[(itemNo,startCap)] 
myList = [] 

while itemNo > 0: 
    if (itemNo == 1 or curValue != d[(itemNo-1, startCap)]) and items[itemNo-1][0] < startCap: #item was included 
     myList = [itemNo] + myList 
     startCap -= items[itemNo-1][0] #subtract the capacity 
     curValue -= items[itemNo-1][1] 
    itemNo -= 1 
print myList #outputs [2,3]