[Solved] Consider the following Python code implementing the space-optimized 0/1 Knapsack solution.... What is the output when weights = [10, 20, 30], values = [60, 100, 120], and W = 50? | Dynamic Programming: Knapsack

Dynamic Programming: Knapsack - 0/1 Knapsack Problem

Consider the following Python code implementing the space-optimized 0/1 Knapsack solution. What is the output when weights = [10, 20, 30], values = [60, 100, 120], and W = 50?

def knapsack_space_optimized(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

weights = [10, 20, 30]
values = [60, 100, 120]
W = 50
print(knapsack_space_optimized(weights, values, W))

A240

B180

C160

D220

Step-by-Step Solution

Solution:

Step 1: Trace dp array updates for each item
For item 0 (weight=10, value=60), dp[w] updated for w=50 down to 10, dp[10..50]=60. For item 1 (weight=20, value=100), dp[30]=max(dp[30], dp[10]+100)=160, dp[50]=max(dp[50], dp[30]+100)=220. For item 2 (weight=30, value=120), dp[50]=max(dp[50], dp[20]+120)=max(220, 160+120)=280 but dp[20] is 60, so dp[50]=max(220, 180)=220.
Step 2: Final dp[50] value
The maximum value achievable with capacity 50 is 220.
Final Answer:
Option D -> Option D
Quick Check:
Manual dp tracing confirms max value 220 [OK]

Quick Trick: Trace dp updates backward to avoid overcounting [OK]

Common Mistakes:

MISTAKES

Forwards iteration over w causes overcounting items.

Trap Explanation:

PITFALL

Forgetting to iterate w backward leads to incorrect dp values and wrong answer.

Interviewer Note:

CONTEXT

Tests ability to mentally execute space-optimized DP and understand iteration order.

Master "0/1 Knapsack Problem" in Dynamic Programming: Knapsack

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

More Dynamic Programming: Knapsack Quizzes

Consider the following Python code implementing the space-optimized 0/1 Knapsack solution. What is the output when weights = [10, 20, 30], values = [60, 100, 120], and W = 50?

Step 1: Trace dp array updates for each item

Step 2: Final dp[50] value

Final Answer:

Quick Check:

Want More Practice?