PythiloLesson 7 of 8 · progress kept in this browser

Use descending capacity for 0/1 knapsack

Each item may be chosen once. A one-dimensional table stores the best value available at every capacity. Updating capacities from high to low is essential: it makes each transition read the previous item set. Updating upward would reuse the same item repeatedly and solve a different problem.

best = [0, 0, 0, 0]
for capacity in range(3, 1, -1):
    best[capacity] = 5
print(best)
Your task

Write pack(items, capacity). Each item is a (positive_weight, nonnegative_value) pair. Return the greatest total value whose weight fits capacity, choosing each item at most once.