(************** Content-type: application/mathematica **************
CreatedBy='Mathematica 5.0'
Mathematica-Compatible Notebook
This notebook can be used with any Mathematica-compatible
application, such as Mathematica, MathReader or Publicon. The data
for the notebook starts with the line containing stars above.
To get the notebook into a Mathematica-compatible application, do
one of the following:
* Save the data starting with the line of stars above into a file
with a name ending in .nb, then open the file inside the
application;
* Copy the data starting with the line of stars above to the
clipboard, then use the Paste menu command inside the application.
Data for notebooks contains only printable 7-bit ASCII and can be
sent directly in email or through ftp in text mode. Newlines can be
CR, LF or CRLF (Unix, Macintosh or MS-DOS style).
NOTE: If you modify the data for this notebook not in a Mathematica-
compatible application, you must delete the line below containing
the word CacheID, otherwise Mathematica-compatible applications may
try to use invalid cache data.
For more information on notebooks and Mathematica-compatible
applications, contact Wolfram Research:
web: http://www.wolfram.com
email: info@wolfram.com
phone: +1-217-398-0700 (U.S.)
Notebook reader applications are available free of charge from
Wolfram Research.
*******************************************************************)
(*CacheID: 232*)
(*NotebookFileLineBreakTest
NotebookFileLineBreakTest*)
(*NotebookOptionsPosition[ 11114, 226]*)
(*NotebookOutlinePosition[ 11757, 248]*)
(* CellTagsIndexPosition[ 11713, 244]*)
(*WindowFrame->Normal*)
Notebook[{
Cell[CellGroupData[{
Cell["Making Change Greedily", "Title"],
Cell[TextData[{
"by Stan Wagon. \nProblem 1009 for the ",
ButtonBox["Macalester College Problem of the Week",
ButtonData:>{
URL[ "http://mathforum.org/wagon/spring04/p1009.html"], None},
ButtonStyle->"Hyperlink"],
"."
}], "Text"],
Cell[TextData[{
"A system of coins is called \"nice\" if it can represent any amount of \
money and the greedy algorithm -- repeatedly take the largest coin that will \
fit -- for making change always uses the smallest number of coins possible. \
The American system of coins -- 1, 5, 10, 25, 50 -- is nice since, for any \
number of cents A, the greedy algorithm for breaking A into a combination of \
coins will use the minimal number of coins. For example, a greedy breakdown \
of $1.38 is 2 half-dollars, a quarter, a dime, and then 3 pennies, and $1.38 \
cannot be obtained in fewer than 7 coins. Any total can be made by using only \
pennies.\n\nThe old British coin system is another matter. It consisted of a \
halfpenny, a penny, threepence, sixpence, a shilling (12 pence), a florin (24 \
pence), a half-crown (30 pence), a crown (60 pence), and a pound (240 pence). \
We ignore here the guinea, worth 252 pence. And let us take the indivisible \
unit as the halfpenny. This system is not nice: a greedy approach to 48 pence \
would use three coins (half-crown + shilling + sixpence), while it can be \
done using just two florins.\n\nQuestion: What is the largest coin in this \
system whose removal leads to a nice system?\n\nSource: This problem is \
inspired by an amazing algorithm (unpublished, though it can be found on the \
web at ",
ButtonBox["http://citeseer.nj.nec.com/pearson94polynomialtime.html",
ButtonData:>{
URL[ "http://citeseer.nj.nec.com/pearson94polynomialtime.html"], None},
ButtonStyle->"Hyperlink"],
" by David Pearson for determining in very fast time whether a set of coins \
is canonical (which is the technical term for \"nice\" above). I have \
implemented Pearson's algorithm in Mathematica and it is really a beautiful \
thing! Note: The related problem of determining the representation with the \
fewest number of coins is NP-hard. "
}], "Text"],
Cell[BoxData[
\(\(GreedyChange[x_, coins_] :=
Module[{y = x},
Map[\((q = Quotient[y, #]; y -= q\ #; q)\) &, coins]];\)\)], "Input"],
Cell[BoxData[
\(\(CanonicalQ[cc_] :=
Module[{n = Length[cc], ans = True, coins = Reverse[Sort[cc]]},
Do[gr = Take[GreedyChange[coins[\([i - 1]\)] - 1, coins],
j]; \[IndentingNewLine]msum =
1 + Total[gr]; \[IndentingNewLine]w =
gr . Take[coins, j] + coins[\([j]\)]; \[IndentingNewLine]gr1 =
GreedyChange[w, coins]; \[IndentingNewLine]If[
msum < Total[gr1],
ans = StringForm["\", w, gr1,
PadRight[ReplacePart[gr, gr[\([\(-1\)]\)] + 1, \(-1\)], n,
0], Total[gr1], msum]], {i, 2, n}, {j, i,
n}]; \[IndentingNewLine]ans];\)\)], "Input"],
Cell[CellGroupData[{
Cell[BoxData[{
\(\(US = {1, 5, 10, 25, 50};\)\), "\[IndentingNewLine]",
\(CanonicalQ[US]\)}], "Input"],
Cell[BoxData[
\(True\)], "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[BoxData[{
\(\(British =
2 {1/2, 1, 3, 6, 12, 24, 30, 60, 240};\)\), "\[IndentingNewLine]",
\(CanonicalQ[British]\)}], "Input"],
Cell[BoxData[
InterpretationBox["\<\"Minimal example is \\!\\(96\\),greedy = \\!\\({0, \
0, 1, 0, 1, 1, 0, 0, 0}\\),optimal = \\!\\({0, 0, 0, 2, 0, 0, 0, 0, 0}\\), \
\\!\\(3\\),\\!\\(2\\)\"\>",
StringForm[
"Minimal example is ``,greedy = ``,optimal = ``, ``,``", 96, {0, 0, 1,
0, 1, 1, 0, 0, 0}, {0, 0, 0, 2, 0, 0, 0, 0, 0}, 3, 2],
Editable->False]], "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[BoxData[
\(Select[
Table[{British[\([i]\)]/2,
CanonicalQ[British[\([DeleteCases[Range[9], i]]\)]]}, {i,
9}], #[\([2]\)] &]\)], "Input"],
Cell[BoxData[
\({{24, True}, {30, True}}\)], "Output"]
}, Open ]],
Cell[TextData[{
"There are at least two coins that make the British system (or subset we \
mentioned) nice, the 24-pence florin and the 30-pence half-crown. Since the \
problem asked for the larger, we get the half-crown.\n\nComments.\n\n1. This \
problem is inspired by an amazing algorithm (unpublished, though it can be \
found on the web at\n<<",
ButtonBox["http://citeseer.nj.nec.com/pearson94polynomialtime.html",
ButtonData:>{
URL[ "http://citeseer.nj.nec.com/pearson94polynomialtime.html"], None},
ButtonStyle->"Hyperlink"],
">> by David Pearson for determining in very fast time whether a set of \
coins is canonical (which is the technical term for \"nice\" above). I have \
implemented Pearson's algorithm in Mathematica and it is really a beautiful \
thing! Code will be sent out next week. Note: The related problem of \
determining the representation with the fewest number of coins is NP-hard.\n\n\
The Pearson algorithm:\n\nLet C be a set of n coins {c(i)}, where we assume \
c(1) > c(2) > ... > c(n), and c(n) = 1.\nC is called \"canonical\" if the \
greedy algorithm for making change always yields the minimal number of coins.\
\nExample: {50, 25, 10, 5, 1} is canonical\n {64, 50, 25, 10, \
5, 1} is not (75 = 50 + 25 = 64 + 10 + 1 is the smallest bad example)\n\n\
Pearson's (amazing) O(n3) algorithm for determining whether C is canonical.\n\
\nFor each i and j such that 2 ? i ? n and i ? j ? n, do:\n 1. Compute \
the greedy representation of c(i - 1) - 1\n 2. Take the leftmost j \
entries of the result of (1) and add 1 to the jth entry; then pad on the \
right with 0s to get an n-vector M.\n 3. Let w be the number represented \
by M (its dot product with C). Check whether the number of coins in the \
greedy rep'n of w is greater than the number of coins in M. If it is, stop \
and compare w to the smallest such w found in previous iterations. If it is \
smaller, update the previous best to the current w.\n 4. If no such w is \
found, then C is canonical. If some w's have been found, then the smallest \
among them is the minimal example showing that w is not canonical.\n\n\n2. A \
problem I have not thought about: Suppose S a set of coins is not nice. \
Suppose it becomes nice after removal of coin n. And it also becomes nice \
upon removal of coin m. Is it necessarily nice if both m and n are removed?\n\
\nSolution by John Guilford (Agilent) and Stan Wagon.\n\nFirst double the \
values of all the coins to get integers: 480 120 60 48 24 13 6 2 1. Now we \
can simplify things by noting that if each coin (except for the \"1\") is a \
multiple of the next smallest coin, N, then we can make an equivalent problem \
by deleting \"1\" and dividing the rest by N (for the US system this is \
equivalent to ignoring pennies and working in multiples of nickels, which is \
how we usually make change). Doing this repeatedly with 3, 2, and 2, reduces \
the set as follows:\n\n480 120 60 48 24 13 6 2 1 -> 240 60 30 24 12 6 3 1 -> \
80 20 10 8 4 2 1 -> 40 10 5 4 2 1\n\nSo the bad example, 48, becomes 8=5+2+1, \
when 8=4+4 is optimal. So it is natural to consider removing 5 from the list \
(since we want the largest) to see if it then becomes nice. It turns out that \
either works. Let's try 5. This leaves the set 40, 10, 4, 2, 1. The reduction \
trick given above reduces this to 20, 5, 2, 1. We need to prove that this is \
nice. Let us first show that the greedy repn. of any number from 0 to 19 is \
optimal. This can be done by checking each one. Example: 13=5+5+2+1 by \
greedy. But it cannot be done in 3 since the only values obtainable with 3 \
coins are 3, 4, 5, 6, 7, 8, 9, 11, 12, and 15. Similar work shows that all \
values from 0 to 19 are nice. Actually, we will need to know that all values \
up to 34 are nice, and this can be checked by hand.\n\nNow use induction on \
the number of 20s in the greedy repn. of n. Suppose n = (a,b,c,d) where a is \
the number of 20s. If a = 0, this is the base case of the induction, handled \
by the 0-19 case above.\nLet m = n - 20. Then (a-1, b, c, d) is the greedy \
repn. of m, and so it must be the optimal rep. by an inductive assumption. \
The number of coins is K=a+b+c+d-1. We need to show that n cannot be \
represented with this many coins. Suppose it were possible and consider the \
optimal repn. There would have to be at least one 20 coin, for if not the \
repn has the form (0, r, s, t). Then r<4 (else a 20 could be substituted) and \
s <10 and t<2. So the total is at most 15+18+1=34, and we checked that the \
conclusion is good for such totals.\n\nSo we know there is at least one 20 \
coin. Removing it would yield a repn. of m with K-1 coins, contradicting \
optimality of K.\n\nRemoving a 5 in the reduced system corresponds to \
removing a 5 x 2 x 2 x 3 = 60 in the original (doubled) system, and this is \
the same as getting rid of the 30-pence coin, the half-crown. QED.\n\nThe \
Mathematica code above implements the greedy algorithm and then Pearson's \
algorithm. The last bit shows that there are two coins that could have been \
removed, the half-crown or the florin."
}], "Text"]
}, Open ]]
},
FrontEndVersion->"5.0 for Microsoft Windows",
ScreenRectangle->{{0, 1024}, {0, 695}},
WindowSize->{688, 598},
WindowMargins->{{0, Automatic}, {Automatic, 0}}
]
(*******************************************************************
Cached data follows. If you edit this Notebook file directly, not
using Mathematica, you must remove the line containing CacheID at
the top of the file. The cache data will then be recreated when
you save this file from within Mathematica.
*******************************************************************)
(*CellTagsOutline
CellTagsIndex->{}
*)
(*CellTagsIndex
CellTagsIndex->{}
*)
(*NotebookFileOutline
Notebook[{
Cell[CellGroupData[{
Cell[1776, 53, 39, 0, 95, "Title"],
Cell[1818, 55, 250, 7, 52, "Text"],
Cell[2071, 64, 1909, 28, 375, "Text"],
Cell[3983, 94, 155, 3, 50, "Input"],
Cell[4141, 99, 759, 13, 210, "Input"],
Cell[CellGroupData[{
Cell[4925, 116, 111, 2, 50, "Input"],
Cell[5039, 120, 38, 1, 29, "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[5114, 126, 149, 3, 50, "Input"],
Cell[5266, 131, 392, 7, 48, "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[5695, 143, 172, 4, 50, "Input"],
Cell[5870, 149, 58, 1, 29, "Output"]
}, Open ]],
Cell[5943, 153, 5155, 70, 1306, "Text"]
}, Open ]]
}
]
*)
(*******************************************************************
End of Mathematica Notebook file.
*******************************************************************)