Dynamic Programming Solution to the Knapsack Problem

The knapsack problem is a classic problem in dynamic programming. It is described as follows: There is a knapsack with a capacity of C, and there are n items. Each item i has a corresponding weight w_i and value v_i. Our goal is to select some of these items to pack into the knapsack, maximizing the total value of the packed items without exceeding the knapsack's capacity.

This is a typical combinatorial optimization problem that can be solved using a step-by-step dynamic programming approach.

Step 1: Define the State

The core of dynamic programming lies in defining the state and finding the transition relationships between states. We define the following state:

dp[i][j] represents the solution to a subproblem: Considering the first i items (items numbered from 1 to i), the maximum value that can be obtained when the knapsack capacity is j.

Here, i ranges from 0 <= i <= n (considering from 0 items to all n items), and j ranges from 0 <= j <= C (knapsack capacity from 0 to maximum capacity C).

This two-dimensional array dp is the table we ultimately need to fill.

Step 2: Determine the Initial State

Before considering any items, or when the knapsack capacity is 0, the obtainable value is obviously 0.

• First row (i=0): When no items are considered, no matter how large the knapsack capacity j is, the maximum value is 0. That is, dp[0][j] = 0.
• First column (j=0): When the knapsack capacity is 0, no items can be packed regardless of which items are considered, so the maximum value is also 0. That is, dp[i][0] = 0.

Step 3: Establish the State Transition Equation

This is the most crucial step. We now need to think about how to derive dp[i][j] based on known subproblem solutions.

For the i-th item, we have only two choices: pack it into the knapsack or not pack it.

1. Do not pack the i-th item:

   • If we decide not to pack the i-th item, the problem reduces to "the maximum value considering the first i-1 items with knapsack capacity j".
   • This solution has already been calculated and is dp[i-1][j].

2. Pack the i-th item:

   • If we decide to pack the i-th item, we must first ensure that the remaining capacity of the knapsack can accommodate it, i.e., j >= w_i.
   • If it fits, then after packing it, the remaining capacity of the knapsack becomes j - w_i.
   • At this point, our total value equals the value of the i-th item v_i plus "the maximum value considering the first i-1 items with the remaining knapsack capacity j - w_i".
   • This solution is v_i + dp[i-1][j - w_i].

Our goal is to maximize the total value. Therefore, dp[i][j] should take the maximum of these two choices.

Putting it together, the state transition equation is as follows:

If j < w_i (current knapsack capacity j is less than the weight of item i, cannot pack it):
    dp[i][j] = dp[i-1][j] // Can only choose not to pack
Otherwise (current knapsack capacity can pack item i):
    dp[i][j] = max( dp[i-1][j],         // Choice one: do not pack item i
                    v_i + dp[i-1][j - w_i] // Choice two: pack item i
                  )

Step 4: Computation Order and Filling the Table

We have the initial state and the state transition equation. Now we need to determine the order of filling the table. Observing the state transition equation, to compute dp[i][j], we need dp[i-1][j] (the cell directly above) and dp[i-1][j - w_i] (a cell to the upper left).

This means we must fill the entire dp table from top to bottom (i increasing from 1 to n) and from left to right (j increasing from 1 to C). This ensures that when computing each cell, all its prerequisite states have already been computed.

Step 5: Example

Assume knapsack capacity C=5, and the item information is as follows:

We initialize a dp[5][6] table (because i ranges from 0 to 4, and j from 0 to 5).

Initialization (i=0):
dp[0][j] = 0 for all j.

Start filling the table:

• i=1 (consider item 1, weight 2, value 6)

  • j=0,1: Capacity less than 2, cannot pack. dp[1][0]=0, dp[1][1]=dp[0][1]=0
  • j=2,3,4,5: Capacity sufficient. dp[1][j] = max(dp[0][j], 6+dp[0][j-2]) = max(0, 6+0) = 6

• i=2 (consider items 1 and 2, item 2 weight 1, value 3)

  • j=0: Capacity 0, dp[2][0]=0
  • j=1: Can only pack item 2. dp[2][1] = max(dp[1][1], 3+dp[1][0]) = max(0, 3+0)=3
  • j=2: Can pack item 1 or 2. dp[2][2] = max(dp[1][2], 3+dp[1][1]) = max(6, 3+0)=6
  • j=3: dp[2][3] = max(dp[1][3], 3+dp[1][2]) = max(6, 3+6)=9
  • j=4,5: Calculate similarly.

• i=3, i=4...

  • Continue filling the entire table according to the state transition equation.

The final filled table dp[i][j] is as follows (you can try filling it yourself for deeper understanding):

The value at the bottom-right corner dp[4][5] = 13 is our final answer: the maximum value is 13.

Step 6: Space Optimization (Rolling Array)

Observing the state transition equation, dp[i][...] depends only on dp[i-1][...]. This means we do not need to store the entire n x C two-dimensional array; we only need to save two rows (the current row and the previous row). After calculating the i-th row, the data from the i-1-th row is no longer needed and can be overwritten by the i-th row data. This reduces the space complexity from O(n*C) to O(C). This is a common optimization technique called the "rolling array".

Summary

The core steps of the dynamic programming method for solving the knapsack problem are:

1. Define the state dp[i][j].
2. Determine the initial state (first row and first column).
3. Establish the state transition equation, analyzing the two choices of "packing" or "not packing" an item.
4. Determine the computation order to ensure prerequisite states are computed.
5. Fill the table and compute, with the final answer at dp[n][C].
6. Consider space optimization.

This method (the 0-1 knapsack problem) is the foundation for many complex knapsack problems (like the complete knapsack, multiple knapsack) and understanding it is crucial.