← 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?
- A.So dp[c − w] still holds the value from before this item, and the item is used at most once
- B.Because larger capacities are more important
- C.To make the loop faster
- 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 →