0/1 Knapsack Problem

▶

Steps

setup

Initialize dp array with zeros

Create a dp array of size W+1 (51) initialized to zero, representing maximum values achievable with capacities from 0 to 50 before processing any items.

💡 Initialization to zero means no items have been considered yet, so maximum value is zero for all capacities.

Line:

dp = [0] * (W + 1)

💡 Starting with zeros sets the base case for the dynamic programming solution.

fill_row

Start processing item 0 (weight=10, value=60)

Begin iterating over capacities from W=50 down to the weight of item 0 (10) to consider including this item.

💡 Processing items one by one updates dp to reflect maximum values including the current item.

Line:

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

💡 We iterate backwards to avoid using updated dp values in the same iteration, preserving correctness.

fill_cells

Update dp at capacity 50 with item 0

At capacity 50, update dp[50] to max of current dp[50] and dp[40] + 60 (value of item 0). Since dp[40] is 0, dp[50] becomes 60.

💡 This step shows how including the current item can increase the maximum value at a given capacity.

Line:

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

💡 Including item 0 at capacity 50 improves maximum value from 0 to 60.

fill_cells

Update dp at capacity 49 with item 0

At capacity 49, update dp[49] to max of dp[49] and dp[39] + 60. Both dp[49] and dp[39] are 0, so dp[49] becomes 60.

💡 This step repeats the update for a smaller capacity that can still hold item 0.

Line:

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

💡 Including item 0 at capacity 49 also improves maximum value to 60.

fill_cells

Update dp at capacity 10 with item 0

At capacity 10, update dp[10] to max of dp[10] and dp[0] + 60. dp[0] is 0, so dp[10] becomes 60.

💡 This is the smallest capacity that can hold item 0, showing the base update for this item.

Line:

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

💡 Including item 0 at capacity 10 sets dp[10] to 60.

fill_row

Start processing item 1 (weight=20, value=100)

Begin iterating over capacities from 50 down to 20 to consider including item 1.

💡 Processing the second item updates dp to reflect maximum values including items 0 and 1.

Line:

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

💡 We continue updating dp to incorporate the new item’s value where capacity allows.

fill_cells

Update dp at capacity 50 with item 1

At capacity 50, update dp[50] to max of current dp[50] (60) and dp[30] + 100. dp[30] is 60, so dp[50] becomes 160.

💡 Including item 1 plus best value for capacity 30 improves dp[50] from 60 to 160.

Line:

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

💡 Combining item 1 with previous items yields a better total value at capacity 50.

fill_cells

Update dp at capacity 30 with item 1

At capacity 30, update dp[30] to max of dp[30] (60) and dp[10] + 100. dp[10] is 60, so dp[30] becomes 160.

💡 Including item 1 plus best value for capacity 10 improves dp[30] from 60 to 160.

Line:

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

💡 Item 1 combined with item 0 yields a better value at capacity 30.

fill_row

Start processing item 2 (weight=30, value=120)

Begin iterating over capacities from 50 down to 30 to consider including item 2.

💡 Processing the third item updates dp to reflect maximum values including all three items.

Line:

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

💡 We continue updating dp to incorporate the new item’s value where capacity allows.

fill_cells

Update dp at capacity 50 with item 2

At capacity 50, update dp[50] to max of dp[50] (160) and dp[20] + 120. dp[20] is 100, so dp[50] becomes 220.

💡 Including item 2 plus best value for capacity 20 improves dp[50] from 160 to 220.

Line:

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

💡 Combining item 2 with item 1 yields the optimal total value at capacity 50.

fill_cells

Update dp at capacity 40 with item 2

At capacity 40, update dp[40] to max of dp[40] (100) and dp[10] + 120. dp[10] is 60, so dp[40] becomes 180.

💡 Including item 2 plus best value for capacity 10 improves dp[40] from 100 to 180.

Line:

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

💡 Item 2 combined with item 0 yields a better value at capacity 40.

traverse

Final dp array after processing all items

All items have been processed. The dp array now holds the maximum values achievable for each capacity from 0 to 50.

💡 The dp array fully encodes the solution to the knapsack problem for the given input.

Line:

return dp[W]

💡 The maximum value achievable with capacity 50 is dp[50] = 220.

def knapsack_space_optimized(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)  # STEP 1: Initialize dp array
    for i in range(n):  # STEP 2: Process each item
        for w in range(W, weights[i] - 1, -1):  # STEP 2: Iterate capacities backwards
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])  # STEP 3: Update dp[w]
    return dp[W]  # STEP 12: Return final answer

if __name__ == '__main__':
    weights = [10, 20, 30]
    values = [60, 100, 120]
    W = 50
    print(knapsack_space_optimized(weights, values, W))

📊

0/1 Knapsack Problem - Watch the Algorithm Execute, Step by Step

Watching the algorithm fill the dp array from the bottom up reveals the dependency of each state on previous states, making the dynamic programming approach intuitive and clear.

Initializing dp array

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52
i=0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

dp initialized to 0

Item 0 - wt:10 val:60

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52
i=0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

processing item 0

Item 0 - wt:10 val:60

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52
i=0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	60

dp[50] updated to 60

Item 0 - wt:10 val:60

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52
i=0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	60	60

dp[49] updated to 60

Item 0 - wt:10 val:60

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52
i=0	0	0	0	0	0	0	0	0	0	0	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60

dp[10] updated to 60

Item 1 - wt:20 val:100

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52
i=0	0	0	0	0	0	0	0	0	0	0	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60

processing item 1

Item 1 - wt:20 val:100

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52
i=0	0	0	0	0	0	0	0	0	0	0	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	160

dp[50] updated to 160

Item 1 - wt:20 val:100

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51
i=0	0	0	0	0	0	0	0	0	0	0	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	160	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	160

dp[30] updated to 160

Item 2 - wt:30 val:120

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51
i=0	0	0	0	0	0	0	0	0	0	0	60	60	60	60	60	60	60	60	60	60	100	100	100	100	100	100	100	100	100	100	160	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	160

processing item 2

Item 2 - wt:30 val:120

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51
i=0	0	0	0	0	0	0	0	0	0	0	60	60	60	60	60	60	60	60	60	60	100	100	100	100	100	100	100	100	100	100	160	160	160	160	160	160	160	160	160	160	160	220	220	220	220	220	220	220	220	220	220	220

dp[50] updated to 220 (max value)

Item 2 - wt:30 val:120

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51
i=0	0	0	0	0	0	0	0	0	0	0	60	60	60	60	60	60	60	60	60	60	100	100	100	100	100	100	100	100	100	100	160	160	160	160	160	160	160	160	180	160	180	180	180	180	180	180	180	180	180	180	220	220

dp[40] updated to 180

Item 2 - wt:30 val:120

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50
i=0	0	0	0	0	0	0	0	0	0	0	60	60	60	60	60	60	60	60	60	60	100	100	100	100	100	100	100	100	100	100	160	160	160	160	160	160	160	160	180	160	180	180	180	180	180	180	180	180	180	180	220

final answer dp[50] = 220

Key Takeaways

✓ The dp array stores the maximum value achievable for each capacity, updated iteratively for each item.

This insight is hard to see from code alone because the dp array updates are subtle and depend on previous states.

✓ Iterating capacities backwards prevents overwriting dp values needed for future calculations in the same iteration.

This backward iteration is a key trick that ensures correctness but is not obvious without visualization.

✓ The final dp[W] value represents the optimal solution, combining items without exceeding capacity.

Seeing the dp array fill step-by-step clarifies how the algorithm builds up to the final answer.

Practice

1. Consider the following Python code for counting the number of ways to make change. What is the output when calling change(5, [1, 2, 5])?

easy

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Initialize dp array

   dp = [1,0,0,0,0,0] since dp[0]=1.

2. Step 2: Update dp for each coin

   For coin=1: dp becomes [1,1,1,1,1,1]; for coin=2: dp updates to [1,1,2,2,3,3]; for coin=5: dp updates to [1,1,2,2,3,4].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   dp[5] = 4 matches known output [OK]

Hint: Trace dp updates coin by coin [OK]

Common Mistakes:

• Off-by-one in dp indexing
• Confusing permutations with combinations

2. You need to split a positive integer n into at least two positive integers such that the product of these integers is maximized. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Pure brute force recursion exploring all partitions without memoization

B. A greedy approach that always cuts the integer into 3s and 2s

C. Dynamic programming using bottom-up tabulation with state representing maximum product for each integer up to n

D. Divide and conquer by splitting the integer into two halves recursively without caching results

Solution

1. Step 1: Understand problem structure

   The problem requires maximizing product by splitting an integer into parts, which naturally fits a DP approach where subproblems represent maximum product for smaller integers.

2. Step 2: Evaluate options

   Greedy (always cutting 3s) fails on some inputs; brute force recursion is correct but inefficient; divide and conquer without memoization repeats work. Bottom-up DP tabulation efficiently computes all subproblems and combines results.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP tabulation ensures optimal substructure and overlapping subproblems [OK]

Hint: DP tabulation handles overlapping subproblems optimally [OK]

Common Mistakes:

• Believing greedy always works for integer break
• Ignoring memoization in recursion

3. Consider the following Python function implementing the space-optimized subset sum algorithm. Given nums = [2, 3, 7] and S = 5, what is the value of dp[5] after processing all elements?

easy

A. True

B. False

C. IndexError due to out-of-range access

D. None (function does not return a boolean)

Solution

1. Step 1: Trace dp array after processing num=2

   Initially dp=[True, False, False, False, False, False]. After num=2, dp[2]=True because dp[0] was True.

2. Step 2: Trace dp array after processing num=3

   From w=5 down to 3, dp[5]=dp[5] or dp[2]=False or True -> True, dp[3]=dp[3] or dp[0]=False or True -> True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Subset {2,3} sums to 5 -> dp[5] is True [OK]

Hint: Trace dp updates backward to avoid double counting [OK]

Common Mistakes:

• Iterating dp forward causing overcounting
• Off-by-one errors in dp indices

4. The following code attempts to solve the coin change minimum coins problem. Identify the line containing the subtle bug that causes incorrect results or infinite recursion for amount=0.

def coinChange(coins, amount):
    def dfs(rem):
        if rem == 0:
            return 0
        res = float('inf')
        for coin in coins:
            if rem - coin >= 0:
                res = min(res, 1 + dfs(rem - coin))
        return res
    ans = dfs(amount)
    return ans if ans != float('inf') else -1

medium

A. Line 3: Missing base case for rem < 0

B. Line 6: Missing check for rem == 0 before recursion

C. Line 9: Returning res without checking if res is still infinity

D. Line 7: Incorrect condition rem - coin >= 0 instead of rem >= coin

Solution

1. Step 1: Analyze base cases in recursion

   Code handles rem == 0 but lacks base case for rem < 0, but since rem - coin >= 0 check prevents negative rem, no infinite recursion occurs.

2. Step 2: Check return value correctness

   Returning res directly without checking if res is still infinity can cause incorrect results when no valid coin combination exists.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Must check if res is infinity before returning to handle no solution cases correctly [OK]

Hint: Check if result is infinity before returning in recursion [OK]

Common Mistakes:

• Forgetting to handle no solution case
• Assuming rem == 0 base case suffices

5. The following code attempts to compute the minimum number of perfect squares summing to n. Which line contains a subtle bug that can cause incorrect results or infinite loops?

medium

A. Line 3: Missing base case assignment dp[0] = 0

B. Line 2: dp initialization with infinity

C. Line 5: Outer loop from 1 to n

D. Line 7: Inner loop condition j*j <= i

Solution

1. Step 1: Identify base case importance

   dp[0] = 0 is critical because it represents zero squares needed to sum to zero. Without it, dp[0] remains infinity, causing dp[i] updates to use invalid values.

2. Step 2: Analyze impact of missing dp[0] = 0

   Since dp[0] is infinity, expressions like 1 + dp[i - j*j] become infinity, preventing dp[i] from ever updating correctly, leading to infinite loops or wrong results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing dp[0] base case breaks DP initialization [OK]

Hint: dp[0] must be zero to start DP correctly [OK]

Common Mistakes:

• Forgetting dp[0] initialization
• Misplacing loop boundaries