🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← 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?

  1. A.Look at the first row
  2. B.Pick the items with the largest values
  3. C.Walk up from dp[n][W]: if dp[i][c] ≠ dp[i − 1][c], item i was taken, so subtract its weight
  4. 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 →