Given the following partial dp table row for capacity w=0..5 after processing first two items: w: 0 1 2 3 4 5 dp: [0, 0, 10, 10, 10, 20] Weights: [2, 3], Values: [10, 20] Which items were selected to achieve dp[5] = 20?

hard🔄 Reverse Engineer Q9 of Q15

Dynamic Programming: Knapsack - 0/1 Knapsack Problem

AOnly the second item (weight=3, value=20)

BBoth items together (weight=5, value=30)

COnly the first item (weight=2, value=10)

DNo items selected

Step-by-Step Solution

Solution:

Step 1: Analyze dp[5] = 20
Value 20 matches second item's value, weight 3 fits in capacity 5.
Step 2: Check if both items fit
Sum weights 2+3=5, sum values 10+20=30, but dp[5] is 20, so both not selected.
Step 3: Confirm only second item selected
dp[5] = 20 indicates only second item chosen.
Final Answer:
Option A -> Option A
Quick Check:
dp value matches second item alone, not combined [OK]

Quick Trick: dp value equals selected items' total value

Common Mistakes:

MISTAKES

Assuming both items selected without checking dp value
Ignoring capacity constraints

Trap Explanation:

PITFALL

Candidates confuse dp values with sums of all items instead of optimal subset.

Interviewer Note:

CONTEXT

Tests ability to reverse engineer solution from dp table

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

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions

More Dynamic Programming: Knapsack Quizzes

Given the following partial dp table row for capacity w=0..5 after processing first two items: w: 0 1 2 3 4 5 dp: [0, 0, 10, 10, 10, 20] Weights: [2, 3], Values: [10, 20] Which items were selected to achieve dp[5] = 20?

Step 1: Analyze dp[5] = 20

Step 2: Check if both items fit

Step 3: Confirm only second item selected

Final Answer:

Quick Check:

Want More Practice?