Table of Contents
Problem
In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
It is possible to make £2 in the following way:
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can £2 be made using any number of coins?
Solution
Brute Force
可以用穷举法:
200a+100b+50c+20d+10e+5f+2g+h = 200
穷尽a,b,c,d,e,f,g,h所有的可能.a:0~1, b:0~2…., 不过知道a = 1时, b:0, 可缩小a,b,c….大小范围, 见 C++Brute1, 类似的见C++Brute2
Recursion
很直接的方法:
- 用一个200的coin, 没用其它的
- 用零个200的coin, 由最大coin为100的来换零钱200
- 用两个100的coin, 没用其它的
- 用一个100的coin, 由最大coin为50的来换零钱100
- 用零个100的coin, 由最大coin为50的来换零钱200
…..
这里大家应该能看出规律, 用公式表示:
\begin{eqnarray*} f(t, c) = 1 & & if & c =1 &or& t=0 & \newline f(t,c) = \sum_{i=0}^{\left \lfloor \frac{t}{c} \right \rfloor}f(t-ic, s(c)) & & if & c > 1 & and & t>0 & \end{eqnarray*} 其中t是要换的钱, c是当前最大的coin,s(c)是下一个比c小的coin
见 C++Formula, 稍有不同的解法见 C++Formula1
DP
见分析
Answer
73682
Source:C++Formula, C++Formula1, C++Brute1, C++Brute2, dp