Algorithms For Dummies

  Working with Greedy Algorithms 

     285

Interestingly, greedy algorithms resemble how humans solve many simple prob-

lems without using much brainpower or with limited information. For instance, 

when working as cashiers and making change, a human naturally uses a greedy 

approach. You can state the make-change problem as paying a given amount (the 

change) using the least number of bills and coins among the available denomina-

tions. The following Python example demonstrates the make-change problem is 

solvable by a greedy approach. It uses the 1, 5, 10, 20, 50, and 100 USD bills, but 

no coins.

def change(to_be_changed, denomination):

    resulting_change = list()

    for bill in denomination:

        while to_be_changed >= bill:

            resulting_change.append(bill)

            to_be_changed = to_be_changed - bill

    return resulting_change, len(resulting_change)

currency = [100, 50, 20, 10, 5, 1]

amount = 367

print ('Change: %s (using %i bills)'

       % (change(amount, currency)))

Change: [100, 100, 100, 50, 10, 5, 1, 1] (using 8 bills)

The algorithm, encapsulated in the 

change()

 function, scans the denominations 

available, from the largest to the smallest. It uses the largest available currency to 

make change until the amount due is less than the denomination. It then moves 

to the next denomination and performs the same task until it finally reaches the 

lowest denomination. In this way, 

change()

 always provides the largest bill pos-

sible given an amount to deliver. (This is the greedy principle in action.)

Greedy algorithms are particularly appreciated for scheduling problems, optimal 

caching, and compression using Huffman coding. They also work fine for some 

graph  problems.  For  instance,  Kruskal’s  and  Prim’s  algorithms  for  finding  a 

minimum-cost spanning tree and Dijkstra’s shortest-path algorithm are all greedy 

ones (see Chapter 9 for details). A greedy approach can also offer a nonoptimal, yet 

an  acceptable  first  approximation,  solution  to  the  traveling  salesman  problem 

(TSP) and solve the knapsack problem when quantities aren’t discrete. (Chapter 16 

discusses both problems.)