MediumDynamic Programming

0/1 Knapsack

Explanation & Solution

Description

Given an array of item weights, an array of item values, and a knapsack capacity W, determine the maximum value that can be obtained by selecting items such that the total weight does not exceed W. Each item can only be used once.

Input:weights = [1,2,3], values = [6,10,12], W = 5

Output: 22

Explanation: Select items with weights 2 and 3 (total weight = 5), giving values 10 + 12 = 22.

Constraints

1 <= weights.length <= 200
weights.length == values.length
1 <= weights[i] <= 1000
1 <= values[i] <= 1000
1 <= W <= 1000

Approach

Dynamic Programming pattern

1. Define the Subproblem

Let dp[w] represent the maximum value achievable with a knapsack capacity of w
We process items one by one and update the dp array

2. Initialize the DP Array

Create a 1D array dp of size W + 1, filled with zeros
dp[0] = 0 because with zero capacity, no value can be obtained

3. Iterate Over Each Item

For each item i, iterate the capacity w from W down to weights[i]
Iterating backwards ensures each item is used at most once (0/1 property)
If we iterated forwards, we could accidentally pick the same item multiple times

4. Update the DP Table

At each capacity w, decide: skip the current item (keep dp[w]) or take it (dp[w - weights[i]] + values[i])
Take the maximum of these two choices: dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i])

5. Return the Answer

After processing all items, dp[W] holds the maximum value achievable with the full knapsack capacity

Key Insight

The 1D DP optimization reduces space from O(n * W) to O(W) by iterating capacity in reverse order
The reverse iteration guarantees each item is considered only once per subproblem
Time complexity is **O(n * W)** where n is the number of items and W is the capacity

Visualization

Input:

[1, 2, 3], W = 5

—

No animation available

Left (L)Right (R)ConvergedDone

0 steps

Solution Code

Longest Common Subsequence

Partition Equal Subset Sum