CODEWITHSUNDEEP
pythonalgorithmoptimizationknapsack-problembranch-and-bound
Vinay
Vinay

Reputation: 1261

How to to get selected items in Branch and Bound knapsack implementation in python?

I tried the implementation given here for knapsack problem using Branch and Bound.

The solution seems fine but it doesn't give the final selected items to reach the optimal value. Is there a way to get this by changing the following code minimally?

import sys

def bound(vw, v, w, idx):
    if idx >= len(vw) or w > limit:
        return -1
    else:
        while idx < len(vw) and w + vw[idx][1] <= limit:
            v, w, idx = v + vw[idx][0], w + vw[idx][1], idx + 1
        if idx < len(vw):
            v += (limit - w) * vw[idx][0] / (vw[idx][1] * 1.0)
        return v

def knapsack(vw, limit, curValue, curWeight, curIndex):
    global maxValue
    if bound(vw, curValue, curWeight, curIndex) >= maxValue:
        if curWeight + vw[curIndex][1] <= limit:
            maxValue = max(maxValue, curValue + vw[curIndex][0])
            knapsack(vw, limit, curValue + vw[curIndex][0], curWeight + vw[curIndex][1], curIndex + 1)

    if curIndex < len(vw) - 1:
        knapsack(vw, limit, curValue, curWeight, curIndex + 1)

    return maxValue

maxValue = 0

if __name__ == '__main__':
    with open(sys.argv[1] if len(sys.argv) > 1 else sys.exit(1)) as f:
        n, limit = map(int, f.readline().split())
        vw = []
        taken = n * [0]
        for ln in f.readlines():
            vl, wl = map(int, ln.split())
            vw.append([vl, wl, vl / (wl * 1.0)])
    print(knapsack(sorted(vw, key=lambda x: x[2], reverse=True), limit, 0, 0, 0))
    print(taken)

Lets say we have an input file with following contents

4 11
8 4
15 8
4 3
10 5

I am expecting a result like the following

19
0 1 1 0

I wrote my own implementation which gives the above desired output but it's taking too long for large problems like this one

Upvotes: 1

Views: 404

Answers (1)

trincot
trincot

Reputation: 350300

I reorganised the provided code a bit, and then added the logic to keep track of the optimal selection. As you want that selection to be a list of zeroes and ones, I used a bitmap for it (a big integer), and each item gets a bit assigned in that bitmap.

Here is how it would look:

from collections import namedtuple

Item = namedtuple("Item", "value, weight, bit")

def knapsack(items, limit):
    maxValue = 0
    bestTaken = 0
    
    def bound(value, weight, index):
        if index >= len(items) or weight > limit:
            return -1
        else:
            item = items[index]
            while weight + item.weight <= limit:
                value, weight, index = value + item.value, weight + item.weight, index + 1
                if index >= len(items):
                    return value
                item = items[index]
            else:
                return value + (limit - weight) * item.value / item.weight

    def recur(taken, value, weight, index):
        nonlocal maxValue, bestTaken

        if maxValue < value:
            maxValue = value
            bestTaken = taken

        if index < len(items) and bound(value, weight, index) >= maxValue:
            item = items[index]
            if weight + item.weight <= limit:
                recur(taken | item.bit, value + item.value, weight + item.weight, index + 1)
            recur(taken, value, weight, index + 1)

    # Add bit mask for each item:
    items = [Item(*item, 1 << index) for index, item in enumerate(items)]
    items.sort(key=lambda item: -item.value / item.weight)
    recur(0, 0, 0, 0)
    return maxValue, ('{:0{width}b}').format(bestTaken, width=len(items))[::-1]

if __name__ == '__main__':
    # Demo input
    s = """4 11
           8 4
           15 8
           4 3
           10 5"""

    lines = s.splitlines(False)
    _, limit = map(int, lines.pop(0).split())
    items = [tuple(map(int, line.split())) for line in lines]
    value, bits = knapsack(items, limit)
    print("Maximised value:", value)
    print("Item selection:", bits)

Upvotes: 2

Related Questions