CODEWITHSUNDEEP
pythonalgorithmknapsack-problem
Mahadeva
Mahadeva

Reputation: 1637

knapsack branch and bound wrong result

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

Upvotes: 3

Views: 1081

Answers (1)

Mathias Rav
Mathias Rav

Reputation: 2973

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.

Upvotes: 4

Related Questions