Dynamic Programming: Knapsack - 0/1 Knapsack Problem
What is the output of the space-optimized 0/1 Knapsack function when weights = [5], values = [10], and W = 0?
What is the output of the space-optimized 0/1 Knapsack function when weights = [5], values = [10], and W = 0?
medium🧾 Code Trace Q4 of Q15
Step-by-Step Solution
Solution:
Step 1: Initialize dp array
dp = [0] since W=0, only capacity 0 available.Step 2: Loop over items and weights
Inner loop runs from W=0 down to weights[i]=5, but since 0 < 5, loop does not execute.Step 3: Return dp[0]
dp[0] remains 0 as no items can be included.Final Answer:
Option A -> Option AQuick Check:
Capacity zero means no items can be taken -> value 0 [OK]
Quick Trick: Capacity zero -> no items included -> value zero
Common Mistakes:
MISTAKES- Assuming item can be included despite zero capacity
- Loop runs incorrectly with invalid range
Trap Explanation:
PITFALL- Candidates expect non-zero output ignoring capacity zero edge case.
Interviewer Note:
CONTEXT- Tests handling of edge cases and loop boundaries in DP
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