knapsack branch and bound wrong result

algorithm, knapsack-problem, python

Solution

The problem is that you're inserting multiple references to the same `Node()` object into your queue. The fix is to initialize two new `v` objects in each iteration of the while-loop as follows:

    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)

Without these reinitializations, you're modifying the `v` object that you already inserted into the queue. This is different from C++ where the Node objects are values that are implicitly copied into the queue to avoid aliasing problems such as these.

Problem

I have converted the code given at this link into a python version. The code is supposed to calculate the correct value of maximum value to be filled in knapsack of weight `W`. I have attached the code below: ``` #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 ``` The program is supposed to calculate value of 235 for following items inside file `test.data`: ``` 5 10 40 2 50 3.14 100 1.98 95 5 30 3 ``` The first line shows `number of items` and `knapsack weight`. Lines below first line shows the `value` and `weight` of those items. Items are made using a `namedtuple` and sorted according to value/weight. For this problem I am getting 135 instead of 235. What am I doing wrong here? EDIT: I have solved the problem of finding correct items based on branch and bound. If needed, one can check it here

Original source