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 .