Greedy Algorithm

A Greedy Algorithm is one that always chooses the best immediate option. The advantage is that it usually makes decisions simpler, but it may create problems in the long run. It is useful for making programs that don't take long to run. Do not use it in your everyday life.

Example

Problem

If $a$ , $b$ , and $c$ are positive integers, and $\frac1a+\frac1b+\frac1c=\frac67$ , what is $a+b+c$ ?

Solution using the Greedy Algorithm

Let $a\leq b\leq c$ . Obviously, as the denominator decreases, the fraction increases. Therefore, $\frac1a\geq\frac1b\geq\frac1c$ . The least possible value of $a$ is $2$ . Then, $\frac67-\frac12=\frac{5}{14}$ . Again, we find the least possible value of $b$ , which is $3$ . We subtract to get $\frac1{42}$ . Therefore, $c=42$ . Our answer is then $2+3+42=\boxed{\textbf{47}}$ .

Page

Toolbox

Search

Greedy Algorithm

Contents

How to use

Example

Problem

Solution using the Greedy Algorithm

See Also