Greedy Algorithm

Revision as of 01:20, 23 January 2021 by Sweetmango77 (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.

How to use

If you're solving a math problem, and it involves something similar or the same as egyptian fractions, Step $1$: Find the largest fraction with a denominator of a positive integer.

Step $2$: Subtract the number you got from ($1$) from the original fraction.

Step $3$: Repeat until you get a fraction with numerator $1$.

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}}$.

See Also

Wikipedia: Greedy Algorithm