揹包分支和綁定錯誤結果

Question

我已將this link中給出的代碼轉換爲python版本。該代碼應該計算最大值的正確值，以填充揹包重量W。我已附加代碼如下：

#http://www.geeksforgeeks.org/branch-and-bound-set-2-implementation-of-01-knapsack/ 

from queue import Queue 
class Node: 
    def __init__(self): 
     self.level = None 
     self.profit = None 
     self.bound = None 
     self.weight = None 

    def __str__(self): 
     return "Level: %s Profit: %s Bound: %s Weight: %s" % (self.level, self.profit, self.bound, self.weight) 


def bound(node, n, W, items): 
    if(node.weight >= W): 
     return 0 

    profit_bound = int(node.profit) 
    j = node.level + 1 
    totweight = int(node.weight) 

    while ((j < n) and (totweight + items[j].weight) <= W): 
     totweight += items[j].weight 
     profit_bound += items[j].value 
     j += 1 

    if(j < n): 
     profit_bound += (W - totweight) * items[j].value/float(items[j].weight) 

    return profit_bound 

Q = Queue() 

def KnapSackBranchNBound(weight, items, total_items): 
    items = sorted(items, key=lambda x: x.value/float(x.weight), reverse=True) 

    u = Node() 
    v = Node() 

    u.level = -1 
    u.profit = 0 
    u.weight = 0 

    Q.put(u) 
    maxProfit = 0; 

    while not Q.empty(): 
     u = Q.get() 
     if u.level == -1: 
      v.level = 0 

     if u.level == total_items - 1: 
      continue 

     v.level = u.level + 1 
     v.weight = u.weight + items[v.level].weight 
     v.profit = u.profit + items[v.level].value 
     if (v.weight <= weight and v.profit > maxProfit): 
      maxProfit = v.profit; 

     v.bound = bound(v, total_items, weight, items) 
     if (v.bound > maxProfit): 
      Q.put(v) 

     v.weight = u.weight 
     v.profit = u.profit 
     v.bound = bound(v, total_items, weight, items) 
     if (v.bound > maxProfit): 
      # print items[v.level] 
      Q.put(v) 

    return maxProfit 

if __name__ == "__main__": 
    from collections import namedtuple 
    Item = namedtuple("Item", ['index', 'value', 'weight']) 
    input_data = open("test.data").read() 
    lines = input_data.split('\n') 

    firstLine = lines[0].split() 
    item_count = int(firstLine[0]) 
    capacity = int(firstLine[1]) 

    print "running from main" 
    items = [] 

    for i in range(1, item_count+1): 
     line = lines[i] 
     parts = line.split() 
     items.append(Item(i-1, int(parts[0]), float(parts[1]))) 
    kbb = KnapSackBranchNBound(capacity, items, item_count) 
    print kbb 

該程序假設爲以下內部文件test.data項計算的235值：

5 10 
40 2 
50 3.14 
100 1.98 
95 5 
30 3 

第一行顯示number of items和knapsack weight。第一行下方的行顯示這些項目的value和weight。項目使用namedtuple製作並根據價值/重量進行分類。對於這個問題，我得到135而不是235.我在這裏做錯了什麼？

編輯： 我已經解決了基於分支和界限找到正確的項目的問題。如果需要，可以檢查它here

Answer 1

問題是，您將多個引用插入同一個Node()對象到您的隊列中。解決方法是在while循環的每次迭代初始化兩個新v對象如下：

while not Q.empty(): 
     u = Q.get() 
     v = Node()         # Added line 
     if u.level == -1: 
      v.level = 0 

     if u.level == total_items - 1: 
      continue 

     v.level = u.level + 1 
     v.weight = u.weight + items[v.level].weight 
     v.profit = u.profit + items[v.level].value 
     if (v.weight <= weight and v.profit > maxProfit): 
      maxProfit = v.profit; 

     v.bound = bound(v, total_items, weight, items) 
     if (v.bound > maxProfit): 
      Q.put(v) 

     v = Node()         # Added line 
     v.level = u.level + 1      # Added line 
     v.weight = u.weight 
     v.profit = u.profit 
     v.bound = bound(v, total_items, weight, items) 
     if (v.bound > maxProfit): 
      # print(items[v.level]) 
      Q.put(v) 

沒有這些重新初始化，您正在修改你已經插入到隊列中v對象。 這與C++的不同之處在於，Node對象是隱式複製到隊列中的值，以避免出現類似這樣的混淆問題。