 TOPICS # Greedy Algorithm

An algorithm used to recursively construct a set of objects from the smallest possible constituent parts.

Given a set of integers ( , , ..., ) with , a greedy algorithm can be used to find a vector of coefficients ( , , ..., ) such that (1)

where is the dot product, for some given integer . This can be accomplished by letting for , ..., and setting (2)

where is the floor function. Now define the difference between the representation and as (3)

If at any step, a representation has been found. Otherwise, decrement the nonzero term with least , set all for , and build up the remaining terms from (4)

for , ..., 1 until or all possibilities have been exhausted.

For example, McNugget numbers are numbers which are representable using only . Taking and applying the algorithm iteratively gives the sequence (0, 0, 3), (0, 2, 2), (2, 1, 2), (3, 0, 2), (1, 4, 1), at which point . 62 is therefore a McNugget number with (5)

If any integer can be represented with or 1 using a sequence ( , , ...), then this sequence is called a complete sequence.

A greedy algorithm can also be used to break down an arbitrary fraction into an Egyptian fraction in a finite number of steps. For a fraction , find the least integer such that , i.e., (6)

where is the ceiling function. Then find the least integer such that . Iterate until there is no remainder. The algorithm gives two or fewer terms for and , three or fewer terms for , and four or fewer for .

Coin Problem, Complete Sequence, Egyptian Fraction, Frobenius Equation, Frobenius Number, Integer Relation, Knapsack Problem, Levine-O'Sullivan Greedy Algorithm, McNugget Number, Reverse Greedy Algorithm, Square Number, Subset Sum Problem, Sylvester's Sequence

## Explore with Wolfram|Alpha More things to try:

## References Wagon, S. "Greedy Coins." http://library.wolfram.com/infocenter/MathSource/5187/.

Greedy Algorithm

## Cite this as:

Weisstein, Eric W. "Greedy Algorithm." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GreedyAlgorithm.html