動態規劃方法 - 揹包謎題

Question

我想用Python 3.x解決動態規劃（DP）方法中的揹包問題。我的電訊局長指示我們前往this code領先。我試圖實現它，如下所示：

def take_input(infile): 
    f_open = open(infile, 'r') 
    lines = [] 
    for line in f_open: 
     lines.append(line.strip()) 
    f_open.close() 
    return lines 

def create_list(jewel_lines): 
    #turns the jewels into a list of lists 
    jewels_list = [] 
    for x in jewel_lines: 
     weight = x.split()[0] 
     value = x.split()[1] 
     jewels_list.append((int(value), int(weight))) 
    jewels_list = sorted(jewels_list, key = lambda x : (-x[0], x[1])) 
    return jewels_list 

def dynamic_grab(items, max_weight): 
    table = [[0 for weight in range(max_weight+1)] for j in range(len(items)+1)] 

    for j in range(1,len(items)+1): 
     val= items[j-1][0] 
     wt= items[j-1][1] 
     for weight in range(1, max_weight+1): 
      if wt > weight: 
       table[j][weight] = table[j-1][weight] 
      else: 
       table[j][weight] = max(table[j-1][weight],table[j-1][weight-wt] + val) 

    result = [] 
    weight = max_weight 
    for j in range(len(items),0,-1): 
     was_added = table[j][weight] != table[j-1][weight] 

     if was_added: 
      val = items[j-1][0] 
      wt = items[j-1][1] 
      result.append(items[j-1]) 
      weight -= wt 

    return result 

def totalvalue(comb): 
    #total of a combo of items 
    totwt = totval = 0 
    for val, wt in comb: 
     totwt += wt 
     totval += val 
    return (totval, -totwt) if totwt <= max_weight else (0,0) 

#required setup of variables  
infile = "JT_test1.txt" 
given_input = take_input(infile) 
max_weight = int(given_input[0]) 
given_input.pop(0) 
jewels_list = create_list(given_input) 

#test lines 
print(jewels_list) 
print(greedy_grab(jewels_list, max_weight)) 
bagged = dynamic_grab(jewels_list, max_weight) 
print(totalvalue(bagged)) 

樣例如下。它是在格式線[0] = bag_max，線[1：]在形式（重量值）：

575 
125 3000 
50 100 
500 6000 
25 30 

我很困惑，該代碼的邏輯在它返回我元組，我不確定輸出元組代表什麼。我一直在看這一段時間，只是不明白代碼是指向我。任何幫助，將不勝感激。

Answer 1

我假設你指的是由totalvalue返回幷包含在由createlist返回的列表中的元組。這些元組都包含兩個整數。這兩個數字中的第一個是寶石的價值，第二個是寶石的重量。

totalvalue返回的最後一個元組表示可以從輸入寶石列表中選擇的寶石的最大可能值，不超過最大權重。

如果你想要所有寶石的價值，你應該找到totalvalue（jewels_list）。當前的元組不是所有珠寶的價值，而只是珠寶的價值在最大重量範圍內。

Answer 2

輸出元組表示最終解決方案的總值和總權重。

bagged是一個列表，類似於[[125,3000]，[500,6000]]。函數總值只是加起來一切。