Question

What is the time complexity of the optimal solution for the 0/1 Knapsack problem with n items and capacity W using Dynamic Programming?

• A. $O(n + W)$
• B. $O(nW)$
• C. $O(2^n)$
• D. $O(W^2)$

Hint:

$O(nW)$ is considered "Pseudo-Polynomial" because it depends on the numerical value of $W$. If $W$ is extremely large (e.g., $2^n$), the DP approach might actually be slower than simple recursion.

Answer 1

The Correct Option is B

Concept: The 0/1 Knapsack problem involves choosing items to maximize total value without exceeding a weight limit, where each item must either be taken (1) or left (0).
• Subproblem: $dp[i][w]$ represents the maximum value using a subset of the first $i$ items with a maximum capacity $w$.
• Recursion: $dp[i][w] = \max(dp[i-1][w], \text{val}_i + dp[i-1][w - \text{wt}_i])$.

Step 1: Analyzing the table dimensions.
To solve the problem, we create a 2D table of size $(n+1) \times (W+1)$. Each row corresponds to an item, and each column corresponds to a possible weight capacity.

Step 2: Calculating the work per cell.
To fill each cell in the table, we perform a constant number of operations (one comparison and one addition). The calculation for each cell is $O(1)$.

Step 3: Determining total complexity.
Total complexity = (Number of cells) $\times$ (Work per cell). Total = $(n \times W) \times O(1) = O(nW)$.