Knapsack Simulator
Interactive 0/1 Knapsack & Fractional Knapsack Layout
Configuration
Weights Array (w)
Item 1
Item 2
Item 3
Item 4
Profits Array (p)
Item 1
Item 2
Item 3
Item 4
Narrative & Setup
In 0/1 Knapsack, you cannot break items; you either take the whole item or leave it. This is typically solved using dynamic programming tabulation. The grid below is initialized with zeros in the first row (no items) and first column (0 capacity). Click 'Play' or 'Step Forward' below to start the step-by-step tabulation simulation.
DP State Transition Formula
K[i][w] = max( K[i-1][w], p[i] + K[i-1][w - w[i]] )
Where:
- K[i][w]: Max profit for first
iitems with capacityw(Current Cell) - K[i-1][w]: Value when Item
iis excluded (Cell Above) - K[i-1][w - w[i]]: Lookback cell value when Item
iis included (Cell to Left)
Tabulation Matrix
| Items \ Capacity (w) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 (No Item) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Item 1wt: 2 | val: 3 | 0 | — | — | — | — | — | — | — |
Item 2wt: 3 | val: 4 | 0 | — | — | — | — | — | — | — |
Item 3wt: 4 | val: 5 | 0 | — | — | — | — | — | — | — |
Item 4wt: 5 | val: 6 | 0 | — | — | — | — | — | — | — |
History: 1 / 28
Animation Speed — 1000ms
Note: Row 0 and Column 0 are filled with 0. The highlighted cell (Cyan) compares the value directly above it (Amber, representing exclusion) and the value at remaining capacity in the previous row (Emerald, representing inclusion of the item).