🎙 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 4 of 10

In the 1D 0/1 knapsack, why must c go from high to low?

In the 1D 0/1 knapsack, why must c go from high to low?

  1. A.So dp[c − w] still holds the value from before this item, and the item is used at most once
  2. B.Because larger capacities are more important
  3. C.To make the loop faster
  4. D.Because Python ranges cannot go upward
Answer & explanation

Correct answer: So dp[c − w] still holds the value from before this item, and the item is used at most once

Going upward, dp[c − w] may already include the current item, so it gets counted again.

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 →