Why does greedy work for the fractional knapsack but not the 0/1 knapsack?

In the fractional knapsack, items can be split, so taking the highest value-per-weight item first is always safe and provably optimal. In the 0/1 knapsack, items are indivisible, the greedy choice can preclude a better combination, and dynamic programming is required for an exact optimum.

How do you prove a greedy algorithm is correct?

The two standard techniques are the exchange argument, which transforms any optimal solution into the greedy one without worsening it, and the 'greedy stays ahead' argument, which shows the greedy partial solution is at least as good as any other at every step. Matroid theory provides a general sufficient condition.

Greedy Algorithms

Greedy algorithms build a solution incrementally by repeatedly making the choice that looks best at the current step, and are correct precisely when such locally optimal choices provably lead to a globally optimal solution.

Najít téma v PaperMindJiž brzyFind papers & topics

Tools & resources

Stáhnout prezentaci

Learn & explore

VideoJiž brzy

Definition

A greedy algorithm constructs a solution through a sequence of choices, each chosen to optimize some local criterion, never revisiting earlier choices; it is correct only when the locally optimal choices yield a globally optimal result.

Scope

This topic covers the greedy paradigm: the greedy-choice property and optimal substructure that justify it, the standard proof techniques (exchange arguments and the matroid framework), and canonical greedy algorithms including Huffman coding, minimum spanning trees (Kruskal and Prim), Dijkstra's shortest paths, and interval scheduling. It also addresses when greedy strategies serve only as approximation heuristics rather than exact methods.

Core questions

What is the greedy-choice property, and how is it proved for a given problem?
How does an exchange argument show that a greedy choice is safe?
Which problems have matroid structure that guarantees greedy optimality?
When is a greedy method only an approximation rather than an exact algorithm?
How does greedy compare to dynamic programming for the same problem?

Key concepts

greedy-choice property
optimal substructure
exchange argument
matroids
Huffman coding
minimum spanning tree
interval scheduling
fractional knapsack

Key theories

Greedy-choice property and exchange arguments: A problem admits a greedy solution when a globally optimal solution can always be modified to agree with the greedy first choice without loss of optimality; exchange (or 'greedy stays ahead') arguments formalize this.
Matroids and greedy optimality: When the feasible solutions form the independent sets of a weighted matroid, the greedy algorithm always finds a maximum-weight independent set; this unifies results such as the optimality of Kruskal's minimum-spanning-tree algorithm.

Clinical relevance

Greedy algorithms drive widely used systems: Huffman coding in data compression formats, minimum-spanning-tree algorithms in network design, Dijkstra's algorithm in routing and navigation, and greedy scheduling and set-cover heuristics in operating systems and resource allocation.

History

Greedy reasoning appears in classic results such as Kruskal's (1956) and Prim's (1957) minimum-spanning-tree algorithms, Huffman's (1952) optimal prefix codes, and Dijkstra's (1959) shortest-path algorithm. The matroid-theoretic explanation of when greedy methods succeed was developed by Edmonds and others in the 1960s and 1970s.

Key figures

David A. Huffman
Joseph Kruskal
Robert Prim
Edsger W. Dijkstra

Seminal works

dijkstra1959
cormen2009

Frequently asked questions

Why does greedy work for the fractional knapsack but not the 0/1 knapsack?: In the fractional knapsack, items can be split, so taking the highest value-per-weight item first is always safe and provably optimal. In the 0/1 knapsack, items are indivisible, the greedy choice can preclude a better combination, and dynamic programming is required for an exact optimum.
How do you prove a greedy algorithm is correct?: The two standard techniques are the exchange argument, which transforms any optimal solution into the greedy one without worsening it, and the 'greedy stays ahead' argument, which shows the greedy partial solution is at least as good as any other at every step. Matroid theory provides a general sufficient condition.