The 0/1 knapsack problem selects indivisible items to maximize total value without exceeding a fixed capacity. Each item has a weight and value; it must be taken whole or not at all. The same structure models choices such as selecting projects under a budget. section 6.2
Let V(i, c) be the greatest value attainable using the first i items at capacity c. For item i with weight wᵢ and value vᵢ, excluding it gives V(i − 1, c); including it, when wᵢ ≤ c, gives vᵢ + V(i − 1, c − wᵢ). Choose the greater feasible value. The zero-item and zero-capacity cases provide base values of zero. section 6.2.1
Dynamic programming fits because recursive decisions revisit the same states (i, c), and each state's optimum follows from optimal solutions to smaller states. Tabulation computes each distinct state once and reuses it. Greedy choices can miss the global optimum; exhaustive enumeration guarantees it but becomes impractical as item counts grow. section 6.2 section 6.2.1
Capacity seven
For items with (weight, value) pairs (3, 4), (4, 5), (2, 3), and (1, 2), a bottom-up table evaluates each item across capacities zero through seven. Its final value is V(4, 7) = 10. section 6.2.5
Table 6.5 Evaluating Item 4 and completing the solution. The bottom-right cell, 𝑉(4, 7) = 10, gives the maximum value attainable with all four items available and a capacity of 7.
|
Item (𝑖)
|
(𝑤𝑖,
𝑣𝑖)
|
𝑐 = 0
|
𝑐 = 1
|
𝑐 = 2
|
𝑐 = 3
|
𝑐 = 4
|
𝑐 = 5
|
𝑐 = 6
|
𝑐 = 7
|
|
0
|
Base Cases
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
1
|
(3, 4)
|
0
|
0
|
0
|
4
|
4
|
4
|
4
|
4
|
|
2
|
(4, 5)
|
0
|
0
|
0
|
4
|
5
|
5
|
5
|
9
|
|
3
|
(2, 3)
|
0
|
0
|
3
|
4
|
5
|
7
|
8
|
9
|
|
4
|
(1, 2)
|
0
|
2
|
3
|
5
|
6
|
7
|
9
|
10
|
The completed table shows the optimal value at each capacity after all four items are considered. section 6.2.5





