0/1 Knapsack

The Idea

Each item is taken whole or left behind — no halves. For every capacity, compare the best total that ignores this item against its value plus the best total for the capacity left over. Sweeping capacity downwards keeps a single row honest, because a cell is only ever read before this item touched it.

Real-World Example

A rescue drone with a five-kilogram payload choosing among water canisters, a first-aid kit, and a radio beacon. You cannot load two-thirds of a canister, so every decision is a flat yes or no — and the most valuable single item often crowds out two that together are worth more.

The Code

def knapsack(weights, values, cap):
    best = [0] * (cap + 1)                     # best[c] = best value within capacity c
    for w, v in zip(weights, values):
        for c in range(cap, w - 1, -1):        # backwards: this item stays single-use
            best[c] = max(best[c], best[c - w] + v)
    return best[cap]

print(knapsack([3, 4, 5], [30, 50, 60], 8))    # 90
print(knapsack([1, 2, 3], [10, 15, 40], 4))    # 50

def knapsack(weights, values, cap):
  best = [0] * (cap + 1)
  for w, v in zip(weights, values):
      for c in range(cap, w - 1, -1):
          best[c] = max(best[c], best[c - w] + v)
  return best[cap]

print(knapsack([2, 3, 4], [4, 5, 7], 5))