← Quiz: 0/1 Knapsack and Subset Sum: all 10 questions
Quiz: 0/1 Knapsack and Subset Sum · Question 10 of 10
How do you find which items were taken from the 2D table?
How do you find which items were taken from the 2D table?
- A.Look at the first row
- B.Pick the items with the largest values
- C.Walk up from dp[n][W]: if dp[i][c] ≠ dp[i − 1][c], item i was taken, so subtract its weight
- D.It cannot be done
Answer & explanation
Correct answer: Walk up from dp[n][W]: if dp[i][c] ≠ dp[i − 1][c], item i was taken, so subtract its weight
A change between two rows means taking item i improved the answer at that capacity.
Can you get the rest right without peeking?
Take the timed Quiz: 0/1 Knapsack and Subset Sum quiz free. Pass it to earn XP and count towards your certificate.
Start the quiz →