Dynamic programming visualizer

0/1 Knapsack Visualizer

Choose whole items to maximize value without exceeding capacity.

Best O(nW)Average O(nW)Worst O(nW)Space O(nW)
Example Data
items = [A(w:2, v:3), B(w:3, v:4), C(w:4, v:5), D(w:5, v:8)], capacity = 8

DP Table

Ready
Ready to compare 4 items across capacity 8.0/1 Knapsack Visualizer
Item / Capacity012345678No items
0
0
0
0
0
0
0
0
0
Aw:2 v:3
?
?
?
?
?
?
?
?
?
Bw:3 v:4
?
?
?
?
?
?
?
?
?
Cw:4 v:5
?
?
?
?
?
?
?
?
?
Dw:5 v:8
?
?
?
?
?
?
?
?
?
Selected itemsCalculated after completion
UpdatingSourceComputed

Metrics

Computations0
Table updates0
Progress0%
Time taken0.0s

Pseudocode

  1. knapsack(items, capacity)
  2. dp = zero matrix
  3. for each item i
  4. for capacity c from 1 to W
  5. dp[i][c] = dp[i - 1][c]
  6. if weight[i] <= c
  7. include = value[i] + dp[i - 1][c - weight[i]]
  8. exclude = dp[i - 1][c]
  9. dp[i][c] = max(include, exclude)
  10. return dp[n][W]