Knapsack branch and bound in Python
Branch and bound for 0-1 knapsack using the fractional-greedy relaxation as the upper bound.
- File
knapsack_branch_and_bound.py, 56 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/knapsack-branch-and-bound/. The authors are listed in prov/0VCNY1.jsonl.
from collections.abc import Sequence
from fractions import Fraction
def knapsack_branch_and_bound(
values: Sequence[int],
weights: Sequence[int],
capacity: int,
stats: dict[str, int] | None = None,
) -> tuple[int, list[int]]:
"""Solve the 0-1 knapsack problem by depth-first branch and bound.
Values, weights and the capacity are nonnegative integers. The bound is
the floor of the fractional (Dantzig) bound, computed in exact integer
arithmetic. Returns the optimal value and the sorted indices of one
optimal set of items.
"""
if stats is None:
stats = {}
stats.update(nodes=0, max_stack=0)
n = len(values)
# Sort by value per unit weight, nonincreasing; items of weight 0 first.
order = sorted(range(n), key=lambda i: (weights[i] > 0, -Fraction(values[i], weights[i]) if weights[i] else 0, i))
v = [values[i] for i in order]
w = [weights[i] for i in order]
def bound(k: int, cw: int, cv: int) -> int:
room = capacity - cw
for j in range(k, n):
if w[j] <= room:
room -= w[j]
cv += v[j]
else:
return cv + v[j] * room // w[j]
return cv
z = 0 # @line L1
best: tuple[int, ...] = () # @line L1
stack: list[tuple[int, int, int, tuple[int, ...]]] = [(0, 0, 0, ())] # @line L2
while stack: # @line L3
k, cw, cv, chosen = stack.pop() # @line L4
stats["nodes"] += 1
if cv > z: # @line L5
z, best = cv, chosen
if k == n or bound(k, cw, cv) <= z: # @line L6
continue
if bound(k + 1, cw, cv) > z: # @line L7
stack.append((k + 1, cw, cv, chosen)) # @line L8
if cw + w[k] <= capacity: # @line L9
stack.append((k + 1, cw + w[k], cv + v[k], chosen + (k,))) # @line L10
stats["max_stack"] = max(stats["max_stack"], len(stack))
return z, sorted(order[j] for j in best) # @line L11
test_knapsack_branch_and_bound.py 55 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/knapsack-branch-and-bound/. The authors are listed in prov/0VCNY1.jsonl.
import itertools
import math
import random
from knapsack_branch_and_bound import knapsack_branch_and_bound
def brute(values, weights, capacity):
best = 0
for mask in itertools.product([0, 1], repeat=len(values)):
if sum(w for w, m in zip(weights, mask) if m) <= capacity:
best = max(best, sum(v for v, m in zip(values, mask) if m))
return best
def test_example_of_the_page() -> None:
stats: dict[str, int] = {}
assert knapsack_branch_and_bound([40, 30, 50, 10], [2, 5, 10, 5], 16, stats) == (90, [0, 2])
assert stats == {"nodes": 8, "max_stack": 3}
def test_unsorted_input() -> None:
assert knapsack_branch_and_bound([10, 50, 30, 40], [5, 10, 5, 2], 16) == (90, [1, 3])
def test_edges() -> None:
assert knapsack_branch_and_bound([], [], 5) == (0, [])
assert knapsack_branch_and_bound([7], [3], 0) == (0, [])
assert knapsack_branch_and_bound([7], [3], 3) == (7, [0])
assert knapsack_branch_and_bound([4, 6], [0, 0], 0) == (10, [0, 1])
assert knapsack_branch_and_bound([0, 0], [1, 1], 5) == (0, [])
def test_hard_family_of_the_page() -> None:
for n in (6, 10, 14):
stats: dict[str, int] = {}
assert knapsack_branch_and_bound([2] * n, [2] * n, n + 1, stats)[0] == n
assert stats["nodes"] == math.comb(n + 1, n // 2) - 1
def test_random_against_brute_force() -> None:
rng = random.Random(1960)
for _ in range(800):
n = rng.randint(0, 10)
values = [rng.randint(0, 40) for _ in range(n)]
weights = [rng.randint(0, 20) for _ in range(n)]
capacity = rng.randint(0, 60)
z, chosen = knapsack_branch_and_bound(values, weights, capacity)
assert z == brute(values, weights, capacity)
assert len(set(chosen)) == len(chosen)
assert sum(weights[i] for i in chosen) <= capacity
assert sum(values[i] for i in chosen) == z
What the next level needs
- the tests did not run in this build