Algorithms For Dummies

Reaching a good solution

Scientists  and  mathematicians  use  greedy  algorithms  so  often  that  Chapter  15 

covers them in depth. However, it’s important to realize that what you really want 

is a good solution, not just a particular solution. In most cases, a good solution 

provides optimal results of the sort you can measure, but the word good can include 

many meanings, depending on the problem domain. You must ask what problem 

you want to solve and which solution solves the problem in a manner that best 

meets your needs. For example, when working in engineering, you might need to 

weigh solutions that consider weight, size, cost, or other considerations, or per-

haps some combination of all these outputs that meet a specific requirement.

To put this issue into context, say that you build a coin machine that creates change 

for particular monetary amounts using the fewest coins possible (perhaps as part 

of an automatic checkout at a store). The reason to use the fewest coins possible is 

to reduce equipment wear, the weight of coins needed, and the time required to 

make change (your customers are always in a hurry, after all). A greedy solution 

solves  the  problem  by  using  the  largest  coins  possible.  For  example,  to  output 

$0.16 in change, you use a dime ($0.10), a nickel ($0.05), and a penny ($0.01).

A problem occurs when you’re unable to use every coin type in creating a solution. 

The  change  machine  might  be  out  of  nickels,  for  example.  To  provide  $0.40  in 

change, a greedy solution would start with a quarter ($0.25) and a dime ($0.10). 

Unfortunately, there are no nickels, so the coin machine then outputs five pennies 

(5 × $0.01) for a total of seven coins. The optimal solution in this case is to use four 

dimes instead (4 × $0.10). As a result, the greedy algorithm provides a particular 

solution, but not a good (optimal) solution in this case. The change-making prob-

lem receives considerable attention because it’s so hard to solve. You can find addi-

tional information in discussions such as “Combinatorics of the Change-Making 

Problem,”  by  Anna  Adamaszeka  and  Michal  Adamaszek  (see 

http://www. 

sciencedirect.com/science/article/pii/S0195669809001292

 for details).

---

CHAPTER 2