Which of the following problem cannot be solved using greedy approach?
2017
Which of the following problem cannot be solved using greedy approach?
- A.
0-1 knapsack
- B.
Minimum spanning tree
- C.
Huffman code
- D.
Job scheduling
Attempted by 209 students.
Show answer & explanation
Correct answer: A
The correct option is A (0-1 knapsack).
The 0-1 Knapsack problem cannot be solved optimally using a greedy approach because items cannot be broken down into fractions. Taking a locally optimal choice based on maximum value-to-weight ratio may leave empty space in the knapsack, leading to a suboptimal global solution. It requires Dynamic Programming instead.