Dynamic Programming Solution for the Knapsack Problem

Description
The knapsack problem is a classic combinatorial optimization problem, commonly encountered in interviews and practical applications. The problem is described as: Given a set of items, each with a weight and a value, and a knapsack with a capacity C. The goal is to select some items to put into the knapsack such that the total weight does not exceed C, and the total value is maximized. The knapsack problem is divided into the 0-1 knapsack (each item can be selected at most once) and the unbounded knapsack (each item can be selected unlimited times). Here, we focus on the dynamic programming solution for the 0-1 knapsack.

Solution Process
Dynamic programming avoids redundant calculations by breaking down the problem into subproblems. For the 0-1 knapsack, the core idea is to consider items and capacities one by one, constructing a two-dimensional DP table.

1. Define State

   • Let dp[i][j] represent the maximum value that can be obtained by considering the first i items (items numbered from 1 to i) with a knapsack capacity of j.
   • Here, i ranges from 0 to n (n is the total number of items), and j ranges from 0 to C (C is the total knapsack capacity).

2. Initialize Base Cases

   • When the number of items is 0 (i=0), regardless of the capacity, the maximum value is 0: dp[0][j] = 0 (j from 0 to C).
   • When the knapsack capacity is 0 (j=0), regardless of the number of items, the maximum value is 0: dp[i][0] = 0 (i from 0 to n).

3. State Transition Equation
   For each item i and capacity j, there are two cases:

   • Do not select the i-th item: The maximum value equals the result of the first i-1 items with capacity j, i.e., dp[i][j] = dp[i-1][j].
   • Select the i-th item (provided the current capacity j ≥ the weight w_i of item i): The maximum value is the value v_i of item i plus the result of the first i-1 items with the remaining capacity j - w_i, i.e., dp[i][j] = v_i + dp[i-1][j - w_i].
   • Finally, take the maximum of the two cases:
     dp[i][j] = max(dp[i-1][j], v_i + dp[i-1][j - w_i]) (if j ≥ w_i, otherwise, only the first case applies).

4. Table Filling Order

   • Outer loop iterates over items i from 1 to n, inner loop iterates over capacity j from 1 to C. Ensure that when computing dp[i][j], dp[i-1][j] and dp[i-1][j - w_i] have already been computed.

5. Obtain Final Result

   • The maximum value is stored in dp[n][C]. If it's necessary to know which specific items were selected, backtrack through the DP table: start from dp[n][C], if dp[i][j] != dp[i-1][j], it means item i was selected, then jump to dp[i-1][j - w_i] and continue backtracking.

Example
Assume item list: weights w = [2, 3, 4, 5], values v = [3, 4, 5, 6], capacity C=8.

• Build the table: rows i from 0 to 4 (4 items), columns j from 0 to 8.
• After filling the table, dp[4][8] = 10 (select items 2 and 4, weight 3+5=8, value 4+6=10).

Optimization

• Space optimization: Since dp[i] depends only on dp[i-1], a one-dimensional array dp[j] can be used instead, with the inner loop j traversing from C to w_i in reverse order to avoid overwriting the previous state.