Greedy Algorithm

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

Given a set of k integers (a_1, a_2, ..., a_k) with a_1<a_2<...<a_k, a greedy algorithm can be used to find a vector of coefficients (c_1, c_2, ..., c_k) such that


where c·a is the dot product, for some given integer n. This can be accomplished by letting c_i=0 for i=1, ..., k-1 and setting


where |_x_| is the floor function. Now define the difference between the representation and n as


If Delta=0 at any step, a representation has been found. Otherwise, decrement the nonzero c_i term with least i, set all c_j=0 for j<i, and build up the remaining terms from


for j=i-1, ..., 1 until Delta=0 or all possibilities have been exhausted.

For example, McNugget numbers are numbers which are representable using only (a_1,a_2,a_3)=(6,9,20). Taking n=62 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 Delta=0. 62 is therefore a McNugget number with


If any integer n can be represented with c_i=0 or 1 using a sequence (a_1, a_2, ...), 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 a/b, find the least integer x_1 such that 1/x_1<=a/b, i.e.,


where [x] is the ceiling function. Then find the least integer x_2 such that 1/x_2<=a/b-1/x_1. Iterate until there is no remainder. The algorithm gives two or fewer terms for 1/n and 2/n, three or fewer terms for 3/n, and four or fewer for 4/n.

See also

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


Wagon, S. "Greedy Coins."

Referenced on Wolfram|Alpha

Greedy Algorithm

Cite this as:

Weisstein, Eric W. "Greedy Algorithm." From MathWorld--A Wolfram Web Resource.

Subject classifications