A fast solver for the knap-sack problem. This is a branch and bound best-first-search. The bound is derived from the continuous relaxation of the problem, which can be identified as a linear-program and is solved efficiently in 1D by sorting.

Knap_sack.py

import functools
import queue
from random import randint
from random import seed
from random import uniform
from typing import NamedTuple


class Item(NamedTuple):
    id: int
    value: int
    weight: int


@functools.total_ordering
class Node:
    def __init__(self, level: int, items: [Item], weight: int, value: int):
        self.level = level
        self.items = items
        self.weight = weight
        self.value = value

    def append(self, item):
        return self.__class__(
            level=self.level,
            items=self.items + [item],
            weight=self.weight + item.weight,
            value=self.value + item.value
        )

    def __eq__(self, other):
        return self.value == other.value

    def __lt__(self, other):
        return self.value > other.value


def bound(node: Node, items: [Item], bag_size: int):
    weight_, value_ = node.weight, node.value
    for item in items[node.level:]:
        if (weight_ + item.weight) < bag_size:
            weight_ += item.weight
            value_ += item.value
        else:
            remaining = (bag_size - weight_)
            value_ += item.value * remaining / item.weight
            break
    return value_


def branch_and_bound(items: [Item], bag_size: int):
    items = filter(lambda x: x.weight < bag_size, items)
    items = sorted(
        items,  # good initialization accelerates search
        key=lambda x: x.value / x.weight,
        reverse=True,  # descending order
    )
    best = Node(level=-1, weight=0, value=0, items=[])
    q = queue.PriorityQueue()
    q.put(best)

    while not q.empty():
        u = q.get()
        u.level += 1
        if u.level == len(items) - 1:
            continue  # no more items left to consider

        # consider adding item
        v = u.append(items[u.level])
        if v.weight <= bag_size:
            q.put(v)
            if v.value >= best.value:
                best = v

        # consider leaving item out
        if bound(u, items, bag_size) >= best.value:
            q.put(u)
    return best


if __name__ == "__main__":
    seed(0)


    def make_problem(size=1000):
        def rand_item(i):
            return Item(i, randint(0, 100_000), randint(0, 100_000))

        items = [rand_item(i) for i in range(size)]
        weight_ = sum([i.weight for i in items])
        bag_size = int(weight_ * uniform(0.1, 0.5))
        return items, bag_size


    best = branch_and_bound(*make_problem(1_000))
    print(best.value, best.weight, best.items)