TOPICS
Search

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

Delta=n-c·a.
(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

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

62=(1·6)+(4·9)+(1·20).
(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.,

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.

AltStyle によって変換されたページ (->オリジナル) /