0/1 Knapsack

Choose items to maximise value without exceeding a weight limit. Each item is taken whole or not at all — which is what makes the greedy 'best value per kilo' rule wrong and dynamic programming necessary.

time O(n × capacity)

space O(n × capacity)

Input

Press Tab out of the box or click Resetto regenerate frames from the current input.

Visualization

No frames yet — edit input and click Run.

—

Pseudocode

dp[i][w] = best value using the first i items with limit w
for i in 1..n:
  for w in 0..capacity:
    skip = dp[i-1][w]
    take = value[i] + dp[i-1][w - weight[i]]   // if it fits
    dp[i][w] = max(skip, take)