Dynamic Programming Solution to the Knapsack Problem

Problem Description
The knapsack problem is a classic combinatorial optimization problem: given a set of items, each with a weight and a value, select a subset of items to maximize the total value without exceeding the knapsack's weight capacity. Formally described as:

• Knapsack capacity: \(W\)
• Number of items: \(n\)
• Weight of the \(i\)-th item: \(w_i\), value: \(v_i\)
• Objective: Select a subset of items satisfying \(\sum w_i \leq W\) and maximizing \(\sum v_i\).

Solution Approach
Dynamic Programming solves the problem by breaking it down into subproblems. Defining the state and the state transition equation is key.

Step 1: Define State
Let \(dp[i][j]\) represent the maximum value achievable when considering the first \(i\) items (items numbered from 1 to i) and with a knapsack capacity of \(j\).

Step 2: Initialization

• When the number of items is 0 (\(i=0\)) or the knapsack capacity is 0 (\(j=0\)), the maximum value is 0:
  \(dp[0][j] = 0\), \(dp[i][0] = 0\).

Step 3: State Transition Equation
For each item \(i\) and each capacity \(j\):

1. If the current item's weight \(w_i > j\): Cannot be taken. Inherit the result from the first \(i-1\) items:
   \(dp[i][j] = dp[i-1][j]\).
2. If \(w_i \leq j\): There are two choices:
   • Do not take it: Value is \(dp[i-1][j]\).
   • Take it: Value is \(dp[i-1][j - w_i] + v_i\) (maximum value for remaining capacity \(j-w_i\) plus the current item's value).
     Take the maximum of the two:
     \(dp[i][j] = \max(dp[i-1][j], dp[i-1][j - w_i] + v_i)\).

Step 4: Tabulation
Iterate sequentially through \(i\) from 1 to \(n\) and \(j\) from 1 to \(W\), filling the 2D array \(dp\). The final answer is at \(dp[n][W]\).

Step 5: Space Optimization
Since \(dp[i][j]\) only depends on data from the previous row \(i-1\), the 2D array can be optimized to a 1D array \(dp[j]\):

• Traverse \(j\) in reverse order from \(W\) down to \(w_i\) (to avoid overwriting data from the previous row):
  \(dp[j] = \max(dp[j], dp[j - w_i] + v_i)\).

Example Demonstration
Assume the item information is as follows (\(n=4, W=8\)):

Optimized 1D DP Calculation Process (Initial \(dp[j] = 0\)):

1. Item 1 (weight 2, value 3):
   • \(j=8\) down to \(2\): \(dp[8] = \max(0, dp[6]+3)=3\), similarly update \(dp[7]\) down to \(dp[2]\) to 3.
2. Item 2 (weight 3, value 4):
   • \(j=8\): \(dp[8] = \max(3, dp[5]+4)=7\) (taking items 2 and 1).
   • Update other capacities similarly.
3. Items 3 and 4: Continue updating analogously. The final result is \(dp[8] = 10\) (selecting items 2 and 4, weight 3+5=8, value 4+6=10).

Key Points Summary

• The core of dynamic programming is overlapping subproblems and optimal substructure.
• Space optimization requires attention to the traversal order to avoid recomputation.
• Time complexity: \(O(nW)\), Space complexity: \(O(W)\).