0/1 knapsack: the idea
Prerequisites: Arrays, integer capacity, and maximizing a value.
Each item has a positive integer weight and a nonnegative value. The task is to maximize total value without exceeding a capacity, using each item at most once. Table entry dp[i][c] is the best value using only the first i items with capacity c. Either skip item i, taking dp[i−1][c], or take it if it fits, adding its value to dp[i−1][c−weight]. Both choices consult the previous row, so an item cannot be reused.
Try it
Start with weights 2, 3, 4, values 4, 5, 7, and capacity 5. The optimum takes items 1 and 2 for value 9. Watch each cell consult the row above, then follow the reconstruction path to see which items were chosen. Try reducing capacity to 3.
Reading the display
Rows represent how many items are available; columns represent capacity. Pink marks the current cell, amber marks consulted subproblems, and green follows the final reconstruction. A dot means the cell is not computed. The table scrolls inside its own panel on mobile.
Time and memory
O(nC) table work and O(nC) storage, where n is item count and C is integer capacity. This is pseudopolynomial: C itself can be exponential in the number of bits used to encode it.
The bounds above describe core work on prepared input. String conversion to code-point arrays and editor validation are additional work. The visualization saves the data at each operation so you can step backward. This recording requires extra time and memory beyond the algorithm’s own working storage. Input limits keep the demonstrations manageable.
When to use it—and what to watch
This solves indivisible-item knapsack, not fractional knapsack. Values need not increase with weights. Equal-valued take and skip choices prefer skipping the current item; there may be several optimal selections.
Continue exploring
- Fibonacci tabulation — Store smaller answers and build the next Fibonacci number.