Dynamic Programming: Knapsack - 0/1 Knapsack Problem
Given the following space-optimized 0/1 Knapsack code, what is the output when weights = [1, 3, 4], values = [10, 40, 50], and W = 6?
Given the following space-optimized 0/1 Knapsack code, what is the output when weights = [1, 3, 4], values = [10, 40, 50], and W = 6?
easy🧾 Code Trace Q3 of Q15
Step-by-Step Solution
Solution:
Step 1: Trace dp array updates for each item
Item 1 (weight=1, value=10): dp[1..6] updated to 10, dp=[0,10,10,10,10,10,10]Step 2: Add item 2 (weight=3, value=40)
Update dp[6]=max(dp[6], dp[3]+40)=max(10,10+40)=50, dp[5]=max(10,dp[2]+40)=50, dp[4]=max(10,dp[1]+40)=50, dp[3]=max(10,dp[0]+40)=40Step 3: Add item 3 (weight=4, value=50)
Update dp[6]=max(50, dp[2]+50)=max(50,10+50)=60, dp[5]=max(50, dp[1]+50)=60, dp[4]=max(50, dp[0]+50)=50Step 4: Final dp array: [0,10,10,40,50,60,60]
Maximum value at capacity 6 is 60.Final Answer:
Option B -> Option BQuick Check:
Maximum value achievable is 60, not 90 [OK]
Quick Trick: Trace dp updates backward to find max value
Common Mistakes:
MISTAKES- Adding values without checking weight constraints
- Forgetting reverse iteration in dp
Trap Explanation:
PITFALL- Candidates often miscalculate dp updates or forget reverse iteration causing wrong max values.
Interviewer Note:
CONTEXT- Tests ability to mentally execute space-optimized DP code
Master "0/1 Knapsack Problem" in Dynamic Programming: Knapsack
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Dynamic Programming: Knapsack Quizzes