Why does the value/weight ratio greedy strategy not always solve 0/1 knapsack optimally?
Athe ratio computation is too slow
Bgreedy is forbidden by NP-completeness
Citems must be sorted in linear time, but sorting needs n log n
Ditems can't be split, so a high-ratio item may block better combinations
Answer & Solution
Correct answer: D. items can't be split, so a high-ratio item may block better combinations
0/1 forbids splitting. Greedy may grab a single high-ratio item that fills most of the knapsack, leaving no room for two slightly-lower-ratio items whose combined value would have been higher. Fractional knapsack avoids this trap by letting you take a fraction of the next item. The non-splittability of 0/1 is exactly what breaks greedy.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for