A greedy algorithm repeatedly chooses the best immediate option according to a criterion. That local choice can produce an optimal answer for some problems, but it can also miss the best overall solution or serve only as an approximation. section 1.3.2
Check whether the local choice fits the problem’s constraints:
- For 0-1 knapsack, choosing food by highest calories or calories per kilogram can block a better combination. section 1.3.2
- For fractional knapsack, sorting by calories per kilogram and taking a fraction of the last item fills the capacity with the best total described. section 1.3.4
- Dijkstra’s algorithm chooses the closest unvisited vertex; negative-weight edges break the assumption that this choice fixes its minimum distance. section 14.4.4
Table 1.2 The list in table 1.1, sorted by calories per kg (view table figure)
The food table ranks items by calories per kilogram, the criterion used for the fractional-knapsack strategy. section 1.3.4
Greedy methods apply only when the problem supports their local choices. When it does not, consider another approach: Bellman-Ford handles negative-weight edges, while brute force or dynamic programming can address the 0-1 knapsack problem. section 14.4.4 section 1.3.5
