Suppose a server has an eight-credit budget. Each cloud instance costs credits and adds processing throughput. Which instances should you run to get the most throughput without overspending? In the 0/1 knapsack problem, every instance must be taken whole or left out: no partial instance is allowed. More generally, choose items with weights and values to maximize total value while keeping total weight at or below capacity W. section 7.0 section 7.1
You could test every combination. That is manageable for four items—16 possibilities—but grows as O(2ⁿ); at 40 items, it exceeds a trillion possibilities. Many choices lead back to the same question: what is the best value available from a given set of earlier items and a given remaining capacity? Dynamic programming saves those answers in a table. section 7.0 section 7.1
Build a table T with one row for each count of available items, from 0 to n, and one column for each capacity, from 0 to W:
- Set row 0 and column 0 to zero: no items or no capacity means no value. section 7.1
- For each item and capacity, copy the value directly above if the item does not fit. section 7.1
- If it fits, compare skipping it, T[i−1, j], with taking it, vᵢ + T[i−1, j−wᵢ]. Record the larger value. Both choices look to the previous row, so the item cannot be taken twice. section 7.1 section 7.4
A choice at capacity three
The first instance costs 1 credit and provides value 2; the second costs 2 and provides value 3. At T[2, 3], skipping the second gives T[1, 3] = 2. Taking it leaves 1 credit, so its value is 3 + T[1, 1] = 5. Record 5. At the full eight-credit budget, the final instance produces another comparison: skip for 10, or take it for 6 + T[3, 3] = 11. The best total value is 11. section 7.1
Figure 7.3 Visualization of the math used to evaluate cell T[2, 3] (circled in green) on the second row (w2 = 2, v2 = 3). The algorithm resolves a binary choice by executing a maximum value comparison between two paths. The exclusion path inherits the value directly above (T[1, 3] = 2). The active inclusion path accepts the new instance's throughput value (v2 = 3, highlighted in the red solid box) and subtracts its weight from the current capacity (3 - 2 = 1), forcing a pointer lookup to the previous row at column 1 (T[1, 1] = 2, highlighted by the red dotted circle). The combined value of 5 outperforms the exclusion path, updating the cell state.
Follow the two arrows into T[2, 3]: one skips the current instance, while the other adds its value to the best result at the leftover capacity. section 7.1
A full table takes O(nW) time and O(nW) space. It makes the choices easy to inspect, though a backward-scanned one-dimensional array can reduce memory use. Check the problem type before using the table: if items can be divided, fractional knapsack instead sorts by value per weight and can take a fraction of the last item. section 7.3 section 7.4





