← Quiz: 0/1 Knapsack and Subset Sum: all 10 questions
Quiz: 0/1 Knapsack and Subset Sum · Question 1 of 10
Why does greedy by value per kg fail for 0/1 knapsack?
Why does greedy by value per kg fail for 0/1 knapsack?
- A.It is too slow
- B.It only works for negative values
- C.Items cannot be split, so one high-ratio item can block a better combination
- D.It always picks the lightest item
Answer & explanation
Correct answer: Items cannot be split, so one high-ratio item can block a better combination
With capacity 7, greedy takes (5 kg, 7) and then (1 kg, 1) for 8, while (3 kg, 4) + (4 kg, 5) gives 9.
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 →