Greedy Algorithm

A greedy algorithm is an algorithm that makes a locally best feasible choice at each step without backtracking. Such choices need not give a globally optimal result.

For a set of positive integers (, , ..., ) with , a greedy coin algorithm starts with the largest denomination and works downward. One seeks a vector of nonnegative integer coefficients (, , ..., ) such that

(1)

where is the dot product, for a given nonnegative integer . Initially let all and set

(2)

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

(3)

The greedy procedure continues by setting

(4)

for , ..., 1, recomputing after each assignment. If , a representation has been found; otherwise the greedy procedure fails, even if a representation exists.

A separate backtracking search can find a representation by decrementing the nonzero with least , resetting all for , recomputing , and greedily filling those lower-denomination coefficients in descending order, recomputing after each assignment. Repeating this process finds a representation or exhausts the finite search space. This extension is a backtracking algorithm.

For example, McNugget numbers are numbers which are representable using only . For , the greedy procedure gives with remainder 2 and fails. Backtracking finds , so 62 is a McNugget number with

(5)

If every positive 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 a fraction , with positive integers , into an Egyptian fraction in a finite number of steps. Find the least integer such that , i.e.,

(6)

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