Making Change

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

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

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

Both versions assume the 6 coin values $1 coin, half dollar, quarter, dime, nickel, penny.   It should be straightforward with version 2 to make the number of coins and their values variables. 
I just noticed a minor problem with the "Max Value"  problem.   Anytime the amount to be changed is not a multiple of some coin value,  there is no limit on how many of that coin will not be able to make change.    The current implementation limits the number of coins, but I suppose a diagnostic message should be given if amount  to be changed is not a multiple of all coin values. 

 

Created January 19, 2002
Modified: February 18, 2016

  

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.