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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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.,

(6)

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
.