[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

Problem Description

There are 293 ways to make change for a dollar using coins of the six denominations $1, 50c, 25c, 10c, 5, 1c.   Can you list them?

Background & Techniques

I found this fact in email of trivia someone sent me the other day.   Along with such gems of knowledge as:

1. An ostrich's eye is bigger that it's brain.
2. The average secretary's left hand does 56% of the typing.
3. A dime has 118 ridges around the edge.

Out of curiosity,  I decided to list the ways to  make change.  Sure enough there are 293,  although # 293, changing a dollar bill with a dollar coin, should hardly count as making change, in my opinion.   

Two versions of the program are included here.  #1 is a beginner's level that solves the problem in the simplest way and displays results in a Listbox.    #2 , intermediate level,   is more generalized, solving money changing making problems for other amounts,  uses a Listview component for better output display and  solves a couple of other money changing problems.

The additional problems are:

What is the smallest number of coins in a set that could not possibly have a total value of $1?  In other words,  we can make change for $1 with  1 coin ( $1 coin);   2 coins (2 half dollars);  3 coins (a half dollar and 2 quarters),  etc.  If we continue this way, at what number can we not find a combination that totals  $1?

The second problem: What is the largest possible value of the set of coins that cannot be used to change $1?  

Source code download includes both versions.  Executable download includes version #2 only.   

Non- programmers can jump to the bottom of the page to download the program.

For Programmers

The simplest way to solve the problem is to generate all feasible combinations of coins and see which ones add up to $1.  "Feasible" means that we might as well limit the number of any particular coin to one dollar's worth (5 quarters plus any other combination of coins will never add up to $1).

Here's the essential code from Making Change #1:

   for c100:=0 to 1 do {dollars}   {Try all feasible combinations of coins}
    for c50:=0 to 2 do {half dollars}
      for c25:=0 to 4 do {quarters}
        for c10:=0 to 10 do {dimes}
          for c5:= 0 to 20 do {nickels}
            for c1:=0 to 100 do {pennies}
            begin
              val:=c100*100+c50*50+c25*25+c10*10+c5*5+c1;
              if val =100 then {total of selected coins is $1.00}
              begin
                inc(count); {increment the count of solutions}
                {display solution here}
              end;

Since there are less than 700,000 subsets to test, this runs quickly and answers the question.  However it is not very flexible - it wouldn't work if we changed the number of coins for example, unless we modify the code.

Version 2 replaces the embedded "for" loops with a recursive call.  Coins is a dynamic array of Tcoin records.  Each Tcoin record contains fields Val, the coin value, and Nbr, the count of coins with that value.    The essence of the recursive solution looks like:  

Procedure AccumTots(n, totsSoFar);

begin

    if n<=high(coins) then {this is a valid coin index}

    begin

        for i:= 0 to ChangeAmount div coins[n].val do {vary # coins from 0 to feasible max}
        begin
            coins[n].nbr:=i;
            nexttot:=totsofar+ i*coins[n].val;
            if (nexttot>ChangeAmount) then break; {stop checking if we get more than amount}
            AccumTots(n+1,nexttot); {recursive call with next coin}
        end;
    end
    else   { values have been assigned for each coin, check the total}
    if totsofar=ChangeAmount then {yup, this is the correct change}
    begin
        inc(count);

        {display  solution here}

    end;

There's lots more to the code, including my first use of the TListView component which works pretty well for displaying the output in columns with header information.  Have fun!

Addendum March 25,2004:  A viewer raised some question about the number of ways to make change for $1 today.   (I think he thinks there are only 289, but it wasn't entirely clear.)  In any event I ran the program and couldn't understand my  description of the "Minimum coin set"  problem.    I improved the problem description and changed the  program to list a sample solution for all of the sets of coins that can make change.  

Running/Exploring the Program 

Suggestions for Further Explorations

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2018, Gary Darby    All rights reserved.