Bellman’s principle of optimality: the 0/1 knapsack

Fills a table of optimal values for every prefix of the items and every capacity, then traces back the chosen items. The table is the dynamic-programming “value function”.

import matplotlib.pyplot as plt

from mathematicskit.optimization import knapsack

Six items, capacity 15

values = [10, 13, 7, 8, 15, 4]
weights = [5, 6, 3, 4, 7, 2]
capacity = 15
result = knapsack(values, weights, capacity)
print(f"best value {result.value:.0f} using items {result.items.tolist()} (total weight {result.weight})")

best value 32 using items [0, 2, 4] (total weight 15)

The value table V(i, c)

fig, ax = plt.subplots(figsize=(9, 4))
im = ax.imshow(result.table, cmap="viridis", aspect="auto", origin="lower")
fig.colorbar(im, ax=ax, label="best value")
ax.set_xlabel("capacity c")
ax.set_ylabel("items considered i")
ax.set_title("Bellman's value table for the knapsack problem (1957)")

Text(0.5, 1.0, "Bellman's value table for the knapsack problem (1957)")