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<\ldots<a_k$, a greedy algorithm can be used to find a Vector of coefficients ($c_1$, $c_2$, ..., $c_k$) such that

$$\sum_{i=1}^k c_i a_i={\bf c}\cdot{\bf a}=n,$$ (1)

where ${\bf c}\cdot{\bf 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

$$c_k=\left\lfloor{n\over a_k}\right\rfloor .$$ (2)

Now define the difference between the representation and $n$ as

$$\Delta\equiv n-{\bf c}\cdot{\bf a}.$$ (3)

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

$$c_j=\left\lfloor{\Delta_j\over a_k}\right\rfloor$$ (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

$$62=(1\cdot 6)+(4\cdot 9)+(1\cdot 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 arbitrary fractions into Unit Fractions in a finite number of steps. For a Fraction $a/b$, find the least Integer $x_1$ such that $1/x_1\leq a/b$, i.e.,

$$x_1={\left\lceil{b}\right\rceil \over a},$$ (6)

where $\left\lceil{x}\right\rceil$ is the Ceiling Function. Then find the least Integer $x_2$ such that $1/x_2\leq 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$.

Paul Erdös and E. G. Strays have conjectured that the Diophantine Equation

$${4\over n}={1\over a}+{1\over b}+{1\over c}$$ (7)

always can be solved, and W. Sierpinski conjectured that

$${5\over n}={1\over a}+{1\over b}+{1\over c}$$ (8)

can be solved.

See also Complete Sequence, Integer Relation, Levine-O'Sullivan Greedy Algorithm, McNugget Number, Reverse Greedy Algorithm, Square Number, Sylvester's Sequence, Unit Fraction