liveBook · Manning

Greedy algorithm

As explained in Algorithms Every Programmer Should Know

A greedy algorithm chooses a locally optimal option at each step without accounting for the effects of future choices.

Suppose you must choose items without exceeding a capacity limit. A greedy algorithm makes the choice that looks best right now, without checking how that choice affects later options. That can be wonderfully simple—but will it produce the best total? section 7.1

When the best-looking item gets in the way

With a 10 kg limit, choosing an attractive 6 kg item first leaves 4 kg that cannot be used. Skipping it would allow two 5 kg items with a higher combined value. The first choice looked good locally but blocked the better combination. section 7.1

Capacity constraints matter even before comparing totals. For an eight-credit cloud-instance budget, choosing the two instances with the highest individual throughput values costs nine credits. That choice is invalid, not merely less efficient. For indivisible items, a dynamic-programming matrix instead compares taking and skipping each item across capacities. section 7.1

Greedy selection is not always the wrong tool. In fractional knapsack, materials can be divided: sort them by value per unit of weight, take the most valuable first, and use a fraction of the last material to fill the remaining capacity. This strategy reaches the optimum for that variant because a partly filled gap need not be wasted. section 7.3

The same short-sighted pattern can appear in route search. If an ant colony optimization algorithm gives too much weight to immediate distance, it effectively picks the closest next node each time and ignores information from the swarm. section 8.3

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines local selection and works through failure and success cases, but does not provide a greedy implementation.
Examples
Uses a 10 kg packing choice, an eight-credit cloud-instance budget, and closest-node route selection.
What it assumes
Introduces greedy selection from its definition while using basic item weights, values, and capacity to explain it.
What you can do after
Evaluate/understand when greedy item selection fails because items are indivisible and when fractional selection makes it optimal.
How it connects
Contrasts 0/1 knapsack and dynamic programming with fractional knapsack, and connects excessive heuristic weighting in ant colony optimization to greedy search.

Also explained in

Compare how 16 books explain greedy algorithm →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.