find所需的最less的硬币数量，可以从1到99美分的任何变化
最近我挑战我的同事写一个algorithm来解决这个问题：
find所需的最less的硬币数量，可以从1到99美分的任何变化。 硬币只能是便士（1），镍（5），硬币（10）和宿舍（25），并且必须能够使用这些硬币从1到99（以1分增量）的每个值。
但是，我意识到如果不检查每种可能的硬币组合，我实际上都不知道如何做到这一点。 解决这个问题必须有一个更好的方法，但是我不知道这种types的algorithm的通用名称会被调用，而且我也无法想象一个方法来简化它，除了看每个解决scheme。
我想知道是否有人能指出我正确的方向，或者提出一个更高效的algorithm。
你正在寻找的是dynamic编程 。
实际上，您不必为每个可能的值列举所有可能的组合，因为您可以根据以前的答案来构build它。
你algorithm需要2个参数：
- 可能的硬币值列表，在这里
[1, 5, 10, 25] - 范围来覆盖，在这里
[1, 99]
目标是计算这个范围所需的最小硬币组。
最简单的方法是以自下而上的方式进行：
Range Number of coins (in the minimal set) 1 5 10 25 [1,1] 1 [1,2] 2 [1,3] 3 [1,4] 4 [1,5] 5 [1,5]* 4 1 * two solutions here [1,6] 4 1 [1,9] 4 1 [1,10] 5 1 * experience tells us it's not the most viable one :p [1,10] 4 2 * not so viable either [1,10] 4 1 1 [1,11] 4 1 1 [1,19] 4 1 1 [1,20] 5 1 1 * not viable (in the long run) [1,20] 4 2 1 * not viable (in the long run) [1,20] 4 1 2
这很容易，在每一步我们可以join至多一个硬币，我们只需要知道在哪里。 这归结为范围[x,y]包含在[x,y+1]因此[x,y+1]的最小集合应该包含[x,y]的最小集合。
正如你可能已经注意到的那样，有时候会有不确定性，也就是说多套有相同数量的硬币。 在这种情况下，只能稍后决定放弃哪一个。
应该有可能改善它的运行时间，当注意到添加一枚硬币通常允许你覆盖更大的范围，我认为你添加了它。
例如，请注意：
[1,5] 4*1 1*5 [1,9] 4*1 1*5
我们增加一个镍来覆盖[1,5]但是这使我们免费获得了[1,9] ！
然而，在处理大量input集合[2,3,5,10,25]以覆盖[2,99] ，我不确定如何快速检查新集合覆盖的范围，或者实际上会更有效。
你可以很快find一个上限。
说，你拿三个季度。 那么你只需要用其他硬币填补1-24,26-49,51-74,76-99的“空白”。
平凡地说，这将与2个硬币，1个镍和4个便士一起工作。
所以，3 + 4 + 2 + 1应该是你的硬币数量的上限，当你的蛮力algorithm超过了这个值时，你可以立即停止search。
对于dynamic编程的任何目的，search的其余部分应该足够快。
（编辑：根据Gabe的观察确定答案）
你至less需要4便士，因为你想得到4作为一个改变，你只能用便士来做到这一点。
拥有超过4便士并不是最理想的。 而不是4 + x硬币，你可以有4便士和x镍 – 他们至less跨越相同的范围。
所以你有4便士。
你需要至less1镍，因为你想得到5作为一个变化。
超过1个镍是不理想的。 而不是1 + x镍币，你可以有1镍和x硬币 – 他们跨越至less相同的范围。
所以你有一个镍。
你需要至less2个硬币，因为你想得到20。
这意味着你有4便士，1镍和至less2angular钱。
如果你的硬币less于10个，你将不到3个季度。 但是，使用所有硬币的最大可能变化是4 + 5 + 20 + 50 = 79，还不够。
这意味着你至less有10个硬币。 托马斯的答案显示，事实上，如果你有4便士，1镍，2angular和3分，一切都很好。
我今天一直在学习dynamic编程 ，结果如下：
coins = [1,5,10,25] d = {} # stores tuples of the form (# of coins, [coin list]) # finds the minimum # of coins needed to # make change for some number of cents def m(cents): if cents in d.keys(): return d[cents] elif cents > 0: choices = [(m(cents - x)[0] + 1, m(cents - x)[1] + [x]) for x in coins if cents >= x] # given a list of tuples, python's min function # uses the first element of each tuple for comparison d[cents] = min(choices) return d[cents] else: d[0] = (0, []) return d[0] for x in range(1, 100): val = m(x) print x, "cents requires", val[0], "coins:", val[1]
dynamic编程确实是神奇的。
很好的问题。 这是我想出的逻辑。 testing包括25个less数情况。
class Program { //Allowable denominations const int penny = 1; const int nickel = 5; const int dime = 10; const int quarter = 25; const int maxCurrencyLevelForTest =55; //1-n where n<=99 static void Main(string[] args) { int minPenniesNeeded = 0; int minNickelsNeeded = 0; int minDimesNeeded = 0; int minQuartersNeeded = 0; if (maxCurrencyLevelForTest == penny) { minPenniesNeeded = 1; } else if (maxCurrencyLevelForTest < nickel) { minPenniesNeeded = MinCountNeeded(penny, maxCurrencyLevelForTest); } else if (maxCurrencyLevelForTest < dime) { minPenniesNeeded = MinCountNeeded(penny, nickel - 1); minNickelsNeeded = MinCountNeeded(nickel, maxCurrencyLevelForTest); } else if (maxCurrencyLevelForTest < quarter) { minPenniesNeeded = MinCountNeeded(penny, nickel - 1); minNickelsNeeded = MinCountNeeded(nickel, dime - 1); minDimesNeeded = MinCountNeeded(dime, maxCurrencyLevelForTest); } else { minPenniesNeeded = MinCountNeeded(penny, nickel - 1); minNickelsNeeded = MinCountNeeded(nickel, dime - 1); minDimesNeeded = MinCountNeeded(dime, quarter - 1); var maxPossilbleValueWithoutQuarters = (minPenniesNeeded * penny + minNickelsNeeded * nickel + minDimesNeeded * dime); if (maxCurrencyLevelForTest > maxPossilbleValueWithoutQuarters) { minQuartersNeeded = (((maxCurrencyLevelForTest - maxPossilbleValueWithoutQuarters)-1) / quarter) + 1; } } var minCoinsNeeded = minPenniesNeeded + minNickelsNeeded+minDimesNeeded+minQuartersNeeded; Console.WriteLine(String.Format("Min Number of coins needed: {0}", minCoinsNeeded)); Console.WriteLine(String.Format("Penny: {0} needed", minPenniesNeeded)); Console.WriteLine(String.Format("Nickels: {0} needed", minNickelsNeeded)); Console.WriteLine(String.Format("Dimes: {0} needed", minDimesNeeded)); Console.WriteLine(String.Format("Quarters: {0} needed", minQuartersNeeded)); Console.ReadLine(); } private static int MinCountNeeded(int denomination, int upperRange) { int remainder; return System.Math.DivRem(upperRange, denomination,out remainder); } }
一些结果：当maxCurrencyLevelForTest = 25时
Min Number of coins needed: 7 Penny: 4 needed Nickels: 1 needed Dimes: 2 needed Quarters: 0 needed
当maxCurrencyLevelForTest = 99时
Min Number of coins needed: 10 Penny: 4 needed Nickels: 1 needed Dimes: 2 needed Quarters: 3 needed
maxCurrencyLevelForTest：54
Min Number of coins needed: 8 Penny: 4 needed Nickels: 1 needed Dimes: 2 needed Quarters: 1 needed
maxCurrencyLevelForTest：55
Min Number of coins needed: 9 Penny: 4 needed Nickels: 1 needed Dimes: 2 needed Quarters: 2 needed
maxCurrencyLevelForTest：79
Min Number of coins needed: 9 Penny: 4 needed Nickels: 1 needed Dimes: 2 needed Quarters: 2 needed
maxCurrencyLevelForTest：85
Min Number of coins needed: 10 Penny: 4 needed Nickels: 1 needed Dimes: 2 needed Quarters: 3 needed
代码可以进一步重构我猜。
编辑：正如评论者指出，我误解了这个问题。 （这个问题非常类似于一个基本的CS问题，我看到学院的学生必须解决…） 波手这不是你正在寻找的答案。 这就是说，虽然原来的答案是错误的，我们可以用它作为O（ n ）解决scheme的垫脚石。
所以，下面的错误答案只能解决一个单一的价值（即68美分所需的最小造币），并简单地运行它的每个价值。
changes = [] for amount in xrange(1, 100): # [1, 99] changes.append( run_the_algo_below( amount ) ) # Take the maximum for each coin type. # ie, if run_the_algo_below returns (q, d, n, p): change = [0, 0, 0, 0] for c in changes: change = [max(c[i], change[i] for i in xrange(0, 4)]
现在，这肯定会给你一个有效的答案，但这是一个最小的答案？ （这是更难的部分，目前我的直觉是肯定的，但我还在想这个…）
（ 错误的答案 ）
哇。 循环？ dynamic编程？ 真的是人？
在Python中：
amount = ( your_amount_in_cents ) quarters = amount // 25 dimes = amount % 25 // 10 nickels = amount % 25 % 10 // 5 pennies = amount % 25 % 10 % 5
也许这些模操作中的一些可以被简化…
这并不难，你只需要思考如何在现实生活中做出改变。 你给出宿舍，直到增加另一个季度会把你超过期望的数额，你发出硬币，直到join另一个硬币会把你超过所需的数额，以此类推。 然后，转换为math运算：模和分。 同样的解决scheme适用于美元，将秒转换为HH：MM：SS等。
假设你在谈论美元，你会想要一个贪婪的algorithm： http : //en.wikipedia.org/wiki/Greedy_algorithm
从本质上说，你尝试从最高到最低的所有教派，从每一个硬币中取出尽可能多的硬币，直到你什么也没有剩下。
对于一般情况，请参阅http://en.wikipedia.org/wiki/Change-making_problem ，因为您希望使用dynamic编程或线性编程来查找贪婪algorithm无法工作的任意面值的答案。
在PHP中无法find这种types的问题的一个很好的解决scheme后，我开发了这个function。
它需要任何金额（高达999.99美元），并返回到达该值所需的每个账单/硬币的最小数量的数组。
它首先将该值转换为一个int便士（由于某些原因，当使用标准浮点值时，我会得到最后的错误）。
返还的面额也是便士（即：5000 = $ 50,100 = $ 1等）。
function makeChange($val) { $amountOfMoney = intval($val*100); $cashInPennies = array(10000,5000,2000,1000,500,100,25,10,5,1); $outputArray = array(); $currentSum = 0; $currentDenom = 0; while ($currentSum < $amountOfMoney) { if( ( $currentSum + $cashInPennies[$currentDenom] ) <= $amountOfMoney ) { $currentSum = $currentSum + $cashInPennies[$currentDenom]; $outputArray[$cashInPennies[$currentDenom]]++; } else { $currentDenom++; } } return $outputArray; } $change = 56.93; $output = makeChange($change); print_r($output); echo "<br>Total number of bills & coins: ".array_sum($output); === OUTPUT === Array ( [5000] => 1 [500] => 1 [100] => 1 [25] => 3 [10] => 1 [5] => 1 [1] => 3 ) Total number of bills & coins: 11
这可能是C＃中的通用解决scheme
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace CoinProblem { class Program { static void Main(string[] args) { var coins = new int[] { 1, 5, 10, 25 }; // sorted lowest to highest int upperBound = 99; int numCoinsRequired = upperBound / coins.Last(); for (int i = coins.Length - 1; i > 0; --i) { numCoinsRequired += coins[i] / coins[i - 1] - (coins[i] % coins[i - 1] == 0 ? 1 : 0); } Console.WriteLine(numCoinsRequired); Console.ReadLine(); } } }
我还没有完全想通过…这是太晚了。 我认为在这种情况下答案应该是9，但Gabe说应该是10 …这是什么产生的。 我想这取决于你如何解释这个问题……我们是在寻找能够产生任何值<X的硬币的最less数量，或者使用最less数量的硬币能够产生任何值<X的最less硬币数量？ 例如…我很确定我们可以用9个硬币，没有镍，然后生产9 …你需要…哦，我明白了。 你需要9便士，这是你没有的，因为这不是我们select的…在这种情况下，我认为这个答案是正确的。 只是recursion实现托马斯的想法，但我不知道他为什么停在那里..你不需要蛮横的东西。
编辑：这是错的。
任务
Find the least number of coins required, that can make any change from 1 to 99 cent.
不同于任务
For each single change from 1 to 99 cent, find the least number of coins required.
因为解决scheme可能是一个完全不同的硬币multiset。
假设你没有（1），（5），（10）和（25）分币，但是（1），（3），（5）和（17）分币：你只需要一个（5）硬币; 但从1到5的所有变化，你需要两（1）个硬币和一（3）个硬币，而不是（5）个硬币。
贪婪algorithm从最小值到最大值，关于变化值和硬币值：
With 1x(1) you get all change values below 2. To make a change of 2, you need an additional coin, which could have any value up to 2; choose greedy -> choose the largest -> (1). With 2x(1) you get all change values below 3. To make a change of 3, you need an additional coin, which could have any value up to 3; choose greedy -> choose the largest -> (3). With 2x(1)+1x(3) you get all change values below 6. To make a change of 6, you need an additional coin, which could have any value up to 6; choose greedy -> choose the largest -> (5). and so on...
这在Haskell中：
coinsforchange [1,3,5,17] 99 where coinsforchange coins change = let f (coinssofar::[Int],sumsofar::Int) (largestcoin::Int,wanttogoto::Int) = let coincount=(max 0 (wanttogoto-sumsofar+largestcoin-1))`div`largestcoin in (replicate coincount largestcoin++coinssofar,sumsofar+coincount*largestcoin) in foldl f ([],0) $ zip coins $ tail [c-1|c<-coins] ++ [change]
而在C ++中：
void f(std::map<unsigned,int> &coinssofar,int &sumsofar, unsigned largestcoin, int wanttogoto) { int x = wanttogoto - sumsofar + largestcoin - 1; coinssofar[largestcoin] = (x>0) ? (x / largestcoin) : 0; //returns coinssofar and sumsofar; } std::map<unsigned,int> coinsforchange(const std::list<unsigned> &coins, int change) { std::map<unsigned,int> coinssofar; int sumsofar=0; std::list<unsigned>::const_iterator coin = coins.begin(); unsigned largestcoin = *coin; for( ++coin ; coin!=coins.end() ; largestcoin=*(coin++)) f(coinssofar,sumsofar,largestcoin,(*coin) - 1); f(coinssofar,sumsofar,largestcoin,change); return coinssofar; }
一般来说，如果你有你的硬币COIN []和你的“更改范围”1..MAX，下面应该find最大数量的硬币。
Initialise array CHANGEVAL[MAX] to -1 For each element coin in COIN: set CHANGEVAL[coin] to 1 Until there are no more -1 in CHANGEVAL: For each index I over CHANGEVAL: if CHANGEVAL[I] != -1: let coincount = CHANGEVAL[I] For each element coin in COIN: let sum = coin + I if (COINS[sum]=-1) OR ((coincount+1)<COINS[sum]): COINS[sum]=coincount+1
我不知道在内在条件下检查硬币最小化是否严格来说是必要的。 我会认为，最小的投币链最终会是正确的，但是比抱歉更安全。
一个vb版本
Public Class Form1 Private Sub Button1_Click(ByVal sender As System.Object, _ ByVal e As System.EventArgs) Handles Button1.Click For saleAMT As Decimal = 0.01D To 0.99D Step 0.01D Dim foo As New CashDrawer(0, 0, 0) Dim chg As List(Of Money) = foo.MakeChange(saleAMT, 1D) Dim t As Decimal = 1 - saleAMT Debug.WriteLine(t.ToString("C2")) For Each c As Money In chg Debug.WriteLine(String.Format("{0} of {1}", c.Count.ToString("N0"), c.moneyValue.ToString("C2"))) Next Next End Sub Class CashDrawer Private _drawer As List(Of Money) Public Sub New(Optional ByVal QTYtwoD As Integer = -1, _ Optional ByVal QTYoneD As Integer = -1, _ Optional ByVal QTYfifty As Integer = -1, _ Optional ByVal QTYquarters As Integer = -1, _ Optional ByVal QTYdimes As Integer = -1, _ Optional ByVal QTYnickels As Integer = -1, _ Optional ByVal QTYpennies As Integer = -1) _drawer = New List(Of Money) _drawer.Add(New Money(2D, QTYtwoD)) _drawer.Add(New Money(1D, QTYoneD)) _drawer.Add(New Money(0.5D, QTYfifty)) _drawer.Add(New Money(0.25D, QTYquarters)) _drawer.Add(New Money(0.1D, QTYdimes)) _drawer.Add(New Money(0.05D, QTYnickels)) _drawer.Add(New Money(0.01D, QTYpennies)) End Sub Public Function MakeChange(ByVal SaleAmt As Decimal, _ ByVal amountTendered As Decimal) As List(Of Money) Dim change As Decimal = amountTendered - SaleAmt Dim rv As New List(Of Money) For Each c As Money In Me._drawer change -= (c.NumberOf(change) * c.moneyValue) If c.Count > 0 Then rv.Add(c) End If Next If change <> 0D Then Throw New ArithmeticException Return rv End Function End Class Class Money '-1 equals unlimited qty Private _qty As Decimal 'quantity in drawer Private _value As Decimal 'value money Private _count As Decimal = 0D Public Sub New(ByVal theValue As Decimal, _ ByVal theQTY As Decimal) Me._value = theValue Me._qty = theQTY End Sub ReadOnly Property moneyValue As Decimal Get Return Me._value End Get End Property Public Function NumberOf(ByVal theAmount As Decimal) As Decimal If (Me._qty > 0 OrElse Me._qty = -1) AndAlso Me._value <= theAmount Then Dim ct As Decimal = Math.Floor(theAmount / Me._value) If Me._qty <> -1D Then 'qty? 'limited qty If ct > Me._qty Then 'enough 'no Me._count = Me._qty Me._qty = 0D Else 'yes Me._count = ct Me._qty -= ct End If Else 'unlimited qty Me._count = ct End If End If Return Me._count End Function ReadOnly Property Count As Decimal Get Return Me._count End Get End Property End Class End Class
这是一个简单的Python版本。
#!/usr/bin/env python required = [] coins = [25, 10, 5, 1] t = [] for i in range(1, 100): while sum(t) != i: for c in coins: if sum(t) + c <= i: t.append(c) break for c in coins: while t.count(c) > required.count(c): required.append(c) del t[:] print required
运行时，它会将以下内容输出到stdout。
[1, 1, 1, 1, 5, 10, 10, 25, 25, 25]
代码是不言而喻的（感谢Python！），但基本上algorithm是添加可用的最大的硬币，这不会使您超过当前拍摄的总数，进入您的临时硬币列表（t在这种情况下）。 一旦你find一个特定总数的最有效的一套硬币，确保在所需的列表中至less有许多硬币。 做到这一点，每1至99美分，你就完成了。
我用DP编写了这个类似问题的algorithm，可能有帮助
public class MinimumCoinProblem { private static void calculateMinumCoins(int[] array_Coins, int sum) { int[] array_best = new int[sum]; for (int i = 0; i < sum; i++) { for (int j = 0; j < array_Coins.length; j++) { if (array_Coins[j] <= i && (array_best[i] == 0 || (array_best[i - array_Coins[j]] + 1) <= array_best[i])) { array_best[i] = array_best[i - array_Coins[j]] + 1; } } } System.err.println("The Value is" + array_best[14]); } public static void main(String[] args) { int[] sequence1 = {11, 9,1, 3, 5,2 ,20}; int sum = 30; calculateMinumCoins(sequence1, sum); } }
这里是我的解决scheme，再次在Python中，并使用dynamic编程。 首先，我生成1到99范围内每个金额所需的最小硬币顺序，从这个结果中我可以find每个面额所需要的最大硬币数量：
def min_any_change(): V, C = [1, 5, 10, 25], 99 mxP, mxN, mxD, mxQ = 0, 0, 0, 0 solution = min_change_table(V, C) for i in xrange(1, C+1): cP, cN, cD, cQ = 0, 0, 0, 0 while i: coin = V[solution[i]] if coin == 1: cP += 1 elif coin == 5: cN += 1 elif coin == 10: cD += 1 else: cQ += 1 i -= coin if cP > mxP: mxP = cP if cN > mxN: mxN = cN if cD > mxD: mxD = cD if cQ > mxQ: mxQ = cQ return {'pennies':mxP, 'nickels':mxN, 'dimes':mxD, 'quarters':mxQ} def min_change_table(V, C): m, n, minIdx = C+1, len(V), 0 table, solution = [0] * m, [0] * m for i in xrange(1, m): minNum = float('inf') for j in xrange(n): if V[j] <= i and 1 + table[i - V[j]] < minNum: minNum = 1 + table[i - V[j]] minIdx = j table[i] = minNum solution[i] = minIdx return solution
执行min_any_change()产生我们正在寻找的答案： {'pennies': 4, 'nickels': 1, 'dimes': 2, 'quarters': 3} 。 作为一个testing，我们可以尝试删除任何面额的硬币，并检查是否仍有可能在1..99范围内进行任何更改：
from itertools import combinations def test(lst): sums = all_sums(lst) return all(i in sums for i in xrange(1, 100)) def all_sums(lst): combs = [] for i in xrange(len(lst)+1): combs += combinations(lst, i) return set(sum(s) for s in combs)
如果我们testing上面得到的结果，我们得到一个True ：
test([1, 1, 1, 1, 5, 10, 10, 25, 25, 25])
但是，如果我们移除一个硬币，无论面额如何，我们会得到一个False ：
test([1, 1, 1, 5, 10, 10, 25, 25, 25])
一方面，这已经得到回答。 另一方面，大部分答案需要许多代码。 这个Python的答案不需要很多代码行，只需要很多思路^ _ ^：
div_round_up = lambda a, b: a // b if a % b == 0 else a // b + 1 def optimum_change(*coins): wallet = [0 for i in range(0, len(coins) - 1)] for j in range(0, len(wallet)): target = coins[j + 1] - 1 target -= sum(wallet[i] * coins[i] for i in range(0, j)) wallet[j] = max(0, div_round_up(target, coins[j])) return wallet optimum_change(1, 5, 10, 25, 100) # [4, 1, 2, 3]
这是一个非常简单的缩放algorithm，可能会打破我还没有考虑的input，但我认为它应该是健壮的。 它基本上是这样说的：“为钱包添加一个新的硬币types，偷看下一个硬币typesN，然后添加使target = N - 1所需的新币数量。 它计算出你至less需要ceil((target - wallet_value)/coin_value)来做这件事，而不会检查这是否也会使每个数字都在两者之间。 请注意，语法通过附加最后一个数字“100”来编码“从0到99美分”，因为这会产生适当的最终target 。
它不检查的原因就像“如果可以的话，它会自动的”。 更直接地说，一旦你做了这一步一分钱（价值1），algorithm可以“打破”一个镍（值5）到任何子区间0 – 4.一旦你做了镍，algorithm现在可以“破“一angular钱（价值10）。 等等。
当然，它不需要那些特定的input; 你也可以使用奇怪的货币：
>>> optimum_change(1, 4, 7, 8, 100) [3, 1, 0, 12]
注意它是如何自动忽略这个7硬币的，因为它知道它已经可以用它的变化来“破”8了。
今天在学习https://www.coursera.org/course/bioinformatics时遇到了这个问题;
DPCHANGE(money, coins) MinNumCoins(0) ← 0 for m ← 1 to money MinNumCoins(m) ← ∞ for i ← 1 to |coins| if m ≥ coini if MinNumCoins(m - coini) + 1 < MinNumCoins(m) MinNumCoins(m) ← MinNumCoins(m - coini) + 1 output MinNumCoins(money)
采用逗号分隔的一系列可用的面额和目标金额。
C＃实现：
public static void DPCHANGE(int val, string denoms) { int[] idenoms = Array.ConvertAll(denoms.Split(','), int.Parse); Array.Sort(idenoms); int[] minNumCoins = new int[val + 1]; minNumCoins[0] = 0; for (int m = 1; m <= val; m++) { minNumCoins[m] = Int32.MaxValue - 1; for (int i = 1; i <= idenoms.Count() - 1; i++) { if (m >= idenoms[i]) { if (minNumCoins[m - idenoms[i]] + 1 < minNumCoins[m]) { minNumCoins[m] = minNumCoins[m - idenoms[i]] + 1; } } } } }
正如我所了解的，如果您使用的是标准货币系统值，那么只需一个循环即可轻松计数最less的硬币数量。 只要总是消耗最大币值，如果不可能检查下一个选项。 但是，如果你有像你这样的硬币如1,2,3,4那么它不工作。 我猜硬币有1,2,5,10,25这个概念是为了让人类更容易计算。
这是我的要求 一个有趣的事情是，我们需要检查形成coin_with_max_value（在我们的情况下为25）所需的最小硬币 – 1只。 之后，只需计算这些分币的总和。 从这一点来看，我们只需要添加一定数量的coin_with_max_value，根据总成本和总和的差异，形成总成本中的任意数量。 而已。
因此，对于我们所取得的价值，一旦发现24分钟的硬币：[1,2,2,5,10,10]。 我们只需要每25个超过30（硬币总和）加25个硬币。 99的最终答案是：
[1，2，5，10，10，25，25，25]
9
import itertools import math def ByCurrentCoins(val, coins): for i in range(1, len(coins) + 1): combinations = itertools.combinations(coins, i) for combination in combinations: if sum(combination) == val: return True return False def ExtraCoin(val, all_coins, curr_coins): for c in all_coins: if ByCurrentCoins(val, curr_coins + [c]): return c def main(): cost = 99 coins = sorted([1, 2, 5, 10, 25], reverse=True) max_coin = coins[0] curr_coins = [] for c in range(1, min(max_coin, cost+1)): if ByCurrentCoins(c, curr_coins): continue extra_coin = ExtraCoin(c, coins, curr_coins) if not extra_coin: print -1 return curr_coins.append(extra_coin) curr_sum = sum(curr_coins) if cost > curr_sum: extra_max_coins = int(math.ceil((cost - curr_sum)/float(max_coin))) curr_coins.extend([max_coin for _ in range(extra_max_coins)]) print curr_coins print len(curr_coins)
对于这个问题，贪婪方法比DP或其他方法提供了更好的解决scheme。 贪婪的方法：find最小的面额小于所需的价值，并将其添加到要交付的硬币组。 降低刚刚添加的面额所需的美分，并重复，直到所需的美分为零。
我的解决scheme（贪婪的方法）在Java解决scheme：
public class MinimumCoinDenomination { private static final int[] coinsDenominations = {1, 5, 10, 25, 50, 100}; public static Map<Integer, Integer> giveCoins(int requiredCents) { if(requiredCents <= 0) { return null; } Map<Integer, Integer> denominations = new HashMap<Integer, Integer>(); int dollar = requiredCents/100; if(dollar>0) { denominations.put(100, dollar); } requiredCents = requiredCents - (dollar * 100); //int sum = 0; while(requiredCents > 0) { for(int i = 1; i<coinsDenominations.length; i++) { if(requiredCents < coinsDenominations[i]) { //sum = sum +coinsDenominations[i-1]; if(denominations.containsKey(coinsDenominations[i-1])) { int c = denominations.get(coinsDenominations[i-1]); denominations.put(coinsDenominations[i-1], c+1); } else { denominations.put(coinsDenominations[i-1], 1); } requiredCents = requiredCents - coinsDenominations[i-1]; break; } } } return denominations; } public static void main(String[] args) { System.out.println(giveCoins(199)); } }
示例程序：
#include<stdio.h> #define LEN 9 // array length int main(){ int coins[LEN]={0,0,0,0,0,0,0,0,0}; // coin count int cointypes[LEN]={1000,500,100,50,20,10,5,2,1}; // declare your coins and note here {ASC order} int sum =0; //temp variable for sum int inc=0; // for loop int amount=0; // for total amount printf("Enter Amount :"); scanf("%d",&amount); while(sum<amount){ if((sum+cointypes[inc])<=amount){ sum = sum+ cointypes[inc]; //printf("%d[1] - %d\n",cointypes[inc],sum); //switch case to count number of notes and coin switch(cointypes[inc]){ case 1000: coins[0]++; break; case 500: coins[1]++; break; case 100: coins[2]++; break; case 50: coins[3]++; break; case 20: coins[4]++; break; case 10: coins[5]++; break; case 5: coins[6]++; break; case 2: coins[7]++; break; case 1: coins[8]++; break; } }else{ inc++; } } printf("note for %d in\n note 1000 * %d\n note 500 * %d\n note 100 * %d\n note 50 * %d\n note 20 * %d\n note 10 * %d\n coin 5 * %d\n coin 2 * %d\n coin 1 * %d\n",amount,coins[0],coins[1],coins[2],coins[3],coins[4],coins[5],coins[6],coins[7],coins[8]); }
Here's a simple c# solution using Linq.
internal class Program { public static IEnumerable<Coin> Coins = new List<Coin> { new Coin {Name = "Dime", Value = 10}, new Coin {Name = "Penny", Value = 1}, new Coin {Name = "Nickel", Value = 5}, new Coin {Name = "Quarter", Value = 25} }; private static void Main(string[] args) { PrintChange(34); Console.ReadKey(); } public static void PrintChange(int amount) { decimal remaining = amount; //Order coins by value in descending order var coinsDescending = Coins.OrderByDescending(v => v.Value); foreach (var coin in coinsDescending) { //Continue to smaller coin when current is larger than remainder if (remaining < coin.Value) continue; // Get # of coins that fit in remaining amount var quotient = (int)(remaining / coin.Value); Console.WriteLine(new string('-',28)); Console.WriteLine("{0,10}{1,15}", coin.Name, quotient); //Subtract fitting coins from remaining amount remaining -= quotient * coin.Value; if (remaining <= 0) break; //Exit when no remainder left } Console.WriteLine(new string('-', 28)); } public class Coin { public string Name { get; set; } public int Value { get; set; } } }
Inspired from this https://www.youtube.com/watch?v=GafjS0FfAC0 following
1) optimal sub problem 2) Overlapping sub problem principles introduced in the video
using System; using System.Collections.Generic; using System.Linq; namespace UnitTests.moneyChange { public class MoneyChangeCalc { private static int[] _coinTypes; private Dictionary<int, int> _solutions; public MoneyChangeCalc(int[] coinTypes) { _coinTypes = coinTypes; Reset(); } public int Minimun(int amount) { for (int i = 2; i <= amount; i++) { IList<int> candidates = FulfillCandidates(i); try { _solutions.Add(i, candidates.Any() ? (candidates.Min() + 1) : 0); } catch (ArgumentException) { Console.WriteLine("key [{0}] = {1} already added", i, _solutions[i]); } } int minimun2; _solutions.TryGetValue(amount, out minimun2); return minimun2; } internal IList<int> FulfillCandidates(int amount) { IList<int> candidates = new List<int>(3); foreach (int coinType in _coinTypes) { int sub = amount - coinType; if (sub < 0) continue; int candidate; if (_solutions.TryGetValue(sub, out candidate)) candidates.Add(candidate); } return candidates; } private void Reset() { _solutions = new Dictionary<int, int> { {0,0}, {_coinTypes[0] ,1} }; } } }
testing用例：
using NUnit.Framework; using System.Collections; namespace UnitTests.moneyChange { [TestFixture] public class MoneyChangeTest { [TestCaseSource("TestCasesData")] public int Test_minimun2(int amount, int[] coinTypes) { var moneyChangeCalc = new MoneyChangeCalc(coinTypes); return moneyChangeCalc.Minimun(amount); } private static IEnumerable TestCasesData { get { yield return new TestCaseData(6, new[] { 1, 3, 4 }).Returns(2); yield return new TestCaseData(3, new[] { 2, 4, 6 }).Returns(0); yield return new TestCaseData(10, new[] { 1, 3, 4 }).Returns(3); yield return new TestCaseData(100, new[] { 1, 5, 10, 20 }).Returns(5); } } } }
Solution with greedy approach in java is as below :
public class CoinChange { public static void main(String args[]) { int denominations[] = {1, 5, 10, 25}; System.out.println("Total required coins are " + greeadApproach(53, denominations)); } public static int greeadApproach(int amount, int denominations[]) { int cnt[] = new int[denominations.length]; for (int i = denominations.length-1; amount > 0 && i >= 0; i--) { cnt[i] = (amount/denominations[i]); amount -= cnt[i] * denominations[i]; } int noOfCoins = 0; for (int cntVal : cnt) { noOfCoins+= cntVal; } return noOfCoins; } }
But this works for single amount. If you want to run it for range, than we have to call it for each amount of range.
There are a couple of similar answers up there but my solution with Java seems a little easier to understand. 看一下这个。
public static int findMinimumNumberOfCoins(int inputCents) { // Error Check, If the input is 0 or lower, return 0. if(inputCents <= 0) return 0; // Create the List of Coins that We need to loop through. Start from highest to lowewst. // 25-10-5-1 int[] mCoinsArray = getCoinsArray(); // Number of Total Coins. int totalNumberOfCoins = 0; for(int i=0; i < mCoinsArray.length; i++) { // Get the Coin from Array. int coin = mCoinsArray[i]; // If there is no inputCoin Left, simply break the for-loop if(inputCents == 0) break; // Check If we have a smaller input than our coin // If it's, we need to go the Next one in our Coins Array. // eg, if we have 8, but the current index of array is 10, we need to go to 5. if(inputCents < coin) continue; int quotient = inputCents/coin; int remainder = inputCents%coin; // Add qutient to number of total coins. totalNumberOfCoins += quotient; // Update the input with Remainder. inputCents = remainder; } return totalNumberOfCoins; } // Create a Coins Array, from 25 to 1. Highest is first. public static int[] getCoinsArray() { int[] mCoinsArray = new int[4]; mCoinsArray[0] = 25; mCoinsArray[1] = 10; mCoinsArray[2] = 5; mCoinsArray[3] = 1; return mCoinsArray; }
This the code in c# to find the solution.
public struct CoinCount { public int coinValue; public int noOfCoins; } /// <summary> /// Find and returns the no of coins in each coins in coinSet /// </summary> /// <param name="coinSet">sorted coins value in assending order</param> /// <returns></returns> public CoinCount[] FindCoinsCountFor1to99Collection(int[] coinSet) { // Add extra coin value 100 in the coin set. Since it need to find the collection upto 99. CoinCount[] result = new CoinCount[coinSet.Length]; List<int> coinValues = new List<int>(); coinValues.AddRange(coinSet); coinValues.Add(100); // Selected coin total values int totalCount = 0; for (int i = 0; i < coinValues.Count - 1; i++) { int count = 0; if (totalCount <= coinValues[i]) { // Find the coins count int remainValue = coinValues[i + 1] - totalCount; count = (int)Math.Ceiling((remainValue * 1.0) / coinValues[i]); } else { if (totalCount <= coinValues[i + 1]) count = 1; else count = 0; } result[i] = new CoinCount() { coinValue = coinValues[i], noOfCoins = count }; totalCount += coinValues[i] * count; } return result; }
import java.io.IOException; import java.io.InputStreamReader; import java.util.Scanner; public class LeastNumofCoins { public int getNumofCoins(int amount) { int denominations[]={50,25,10,5,2,1}; int numOfCoins=0; int index=0; while(amount>0) { int coin=denominations[index]; if(coin==amount) { numOfCoins++; break; } if(coin<=amount) { amount=amount-coin; numOfCoins++; } else { index++; } } return numOfCoins; } public static void main(String[] args) throws IOException { Scanner scanner= new Scanner(new InputStreamReader(System.in)); System.out.println("Enter the Amount:"); int amoount=scanner.nextInt(); System.out.println("Number of minimum coins required to make "+ amoount +" is "+new LeastNumofCoins().getNumofCoins(amoount)); scanner.close(); } }
