How to Solve: 0/1 Knapsack Problem

How to Solve: 0/1 Knapsack Problem

(Complete Guide for FAANG-Level Interviews)

? Introduction

"The 0/1 Knapsack problem is the ultimate test of dynamic programming mastery—it appears in 1 out of every 3 onsite interviews at top-tier companies. Nail it, and you prove you can break down complex optimization problems into clean, reusable DP patterns."

? WHAT YOU NEED TO KNOW FIRST

Before tackling 0/1 Knapsack, ensure you understand: 1. Dynamic Programming (DP) Basics – Memoization vs. tabulation, state transitions, and recurrence relations. 2. Time & Space Complexity Analysis – How to compute and optimize for O(nW) vs. O(n) space. 3. Recursive Backtracking – How to model decisions (take/don’t take) and base cases.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

(Repeatable mental checklist for every 0/1 Knapsack problem.)

1. Understand the Problem
2. Confirm it’s a 0/1 Knapsack (items cannot be reused).

3. Identify n (number of items), W (capacity), weights[], values[].

4. Define the DP State

5. dp[i][w] = max value using firstiitems with capacityw`.

6. Base case: dp[0][w] = 0 (no items), dp[i][0] = 0 (zero capacity).

7. Write the Recurrence Relation

8. Option 1: Exclude item i → dp[i-1][w]
9. Option 2: Include item i → dp[i-1][w - weight[i]] + value[i] (if weight[i] <= w)

10. Final: dp[i][w] = max(Option 1, Option 2)

11. Choose Implementation Style

12. Top-Down (Memoization): Recursive + cache (easier to debug).

13. Bottom-Up (Tabulation): Iterative + 2D/1D array (space-optimized).

14. Optimize Space (If Needed)

15. Use 1D array: dp[w] = max(dp[w], dp[w - weight[i]] + value[i])

16. Iterate w from W to 0 to avoid overwriting.

17. Handle Edge Cases

18. n = 0 → Return 0.
19. W = 0 → Return 0.

20. weight[i] > W → Skip item.

21. Test with Small Inputs

22. Manually verify dp table for n=2, W=3.

23. Analyze Complexity

24. Time: O(nW) (pseudo-polynomial).
25. Space: O(W) (1D DP).

? WORKED EXAMPLES

Example 1 – Basic 0/1 Knapsack

Problem: Given weights = [1, 2, 3], values = [6, 10, 12], W = 5, find max value.

Step-by-Step Solution

1. DP State: dp[i][w] = max value using firstiitems with capacityw`.
2. Base Case: dp[0][w] = 0, dp[i][0] = 0.
3. Recurrence:
4. dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])

5. Fill DP Table:
   | i\w | 0 | 1 | 2 | 3 | 4 | 5 |
   |-----|---|---|---|---|---|---|
   | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
   | 1 | 0 | 6 | 6 | 6 | 6 | 6 |
   | 2 | 0 | 6 | 10| 16| 16| 16|
   | 3 | 0 | 6 | 10| 16| 18| 22|

6. Result: dp[3][5] = 22.

Python Code (Top-Down)

def knapsack(weights, values, W):

    n = len(weights)

    memo = [[-1]  (W + 1) for _ in range(n + 1)]


    def dp(i, w):

        if i == 0 or w == 0:

            return 0

        if memo[i][w] != -1:

            return memo[i][w]

        if weights[i-1] > w:

            memo[i][w] = dp(i-1, w)

        else:

            memo[i][w] = max(dp(i-1, w), dp(i-1, w - weights[i-1]) + values[i-1])

        return memo[i][w]


    return dp(n, W)

print(knapsack([1, 2, 3], [6, 10, 12], 5))  # Output: 22

Python Code (Bottom-Up, 1D)

def knapsack(weights, values, W):

    dp = [0]  (W + 1)

    for i in range(len(weights)):

        for w in range(W, weights[i] - 1, -1):

            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[W]

print(knapsack([1, 2, 3], [6, 10, 12], 5))  # Output: 22

Complexity

• Time: O(nW)
• Space: O(W)

Why This Works

• State Definition: dp[i][w] captures all possible subsets of items.
• Recurrence: Explicitly models the "take/don’t take" decision.
• Space Optimization: 1D array works because we only need the previous row.

Example 2 – Medium (Count of Subsets with Given Sum)

Problem: Given nums = [1, 2, 3, 4], target = 6, count subsets that sum to target.

Step-by-Step Solution

1. DP State: dp[i][s] = number of subsets using firstiitems that sum tos`.
2. Base Case: dp[0][0] = 1 (empty subset), dp[0][s>0] = 0.
3. Recurrence:
4. dp[i][s] = dp[i-1][s] + dp[i-1][s - nums[i-1]] (if s >= nums[i-1]).

5. Fill DP Table:
   | i\s | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
   |-----|---|---|---|---|---|---|---|
   | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
   | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
   | 2 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
   | 3 | 1 | 1 | 1 | 2 | 1 | 1 | 1 |
   | 4 | 1 | 1 | 1 | 2 | 2 | 2 | 3 |

6. Result: dp[4][6] = 2 (subsets: [1,2,3], [2,4]).

Python Code (Bottom-Up)

def count_subsets(nums, target):

    dp = [0]  (target + 1)

    dp[0] = 1

    for num in nums:

        for s in range(target, num - 1, -1):

            dp[s] += dp[s - num]

    return dp[target]

print(count_subsets([1, 2, 3, 4], 6))  # Output: 2

Why This Works

• State Transition: Counts subsets by either including or excluding the current number.
• Space Optimization: 1D array suffices because we only need the previous state.

Example 3 – Hard (Minimum Subset Sum Difference)

Problem: Given nums = [1, 6, 11, 5], partition into two subsets with minimum difference.

Step-by-Step Solution

1. Key Insight: Find a subset with sum S/2 (where S = sum(nums)).
2. DP State: dp[i][s] = True if sumscan be formed with firsti` items.
3. Base Case: dp[0][0] = True.
4. Recurrence:
5. dp[i][s] = dp[i-1][s] or dp[i-1][s - nums[i-1]] (if s >= nums[i-1]).
6. Find Closest to S/2:
7. Iterate s from S//2 down to 0 to find the largest s where dp[n][s] is True.
8. Result: abs(S - 2s).

Python Code

def min_subset_diff(nums):

    total = sum(nums)

    n = len(nums)

    dp = [False]  (total // 2 + 1)

    dp[0] = True

    for num in nums:

        for s in range(total // 2, num - 1, -1):

            dp[s] = dp[s] or dp[s - num]

    for s in range(total // 2, -1, -1):

        if dp[s]:

            return abs(total - 2  s)

    return total

print(min_subset_diff([1, 6, 11, 5]))  # Output: 1 (11 vs 12)

Why This Works

• DP State: Tracks achievable sums up to S/2.
• Greedy Search: Finds the closest sum to S/2 to minimize difference.

❌ Common Mistakes

?️ INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. For 0/1 Knapsack, remember: 1. Define dp[i][w] as the max value using the first i items with capacity w. 2. Recurrence: max(exclude, include) where include = dp[i-1][w - weight[i]] + value[i]. 3. Base cases: dp[0][w] = 0, dp[i][0] = 0. 4. Optimize space: Use 1D array and iterate w backward. 5. Edge cases: Skip items where weight[i] > W.

Test with small inputs, and you’ll catch 90% of bugs. Now go crush that interview!

? Final Notes

• Practice Variations: Subset sum, partition problem, target sum.
• Time Yourself: Solve a 0/1 Knapsack problem in 15 minutes (including edge cases).
• Whiteboard First: Always sketch the DP table before coding.

This framework is battle-tested—use it, and you’ll solve any 0/1 Knapsack problem under pressure. ?