[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
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:
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.
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:
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:
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
Copyright © 2000-2017, Gary Darby All rights reserved.