首頁(yè) 猿問(wèn) 如果給出一些美元價(jià)值，如何找到所有...

如果給出一些美元價(jià)值，如何找到所有硬幣組合

源碼算法與數(shù)據(jù)結(jié)構(gòu)

慕蓋茨4494581 2019-08-29 09:10:56

如果給出一些美元價(jià)值，如何找到所有硬幣組合幾個(gè)月前，我找到了一段代碼，我正在編寫面試。根據(jù)我的評(píng)論，它試圖解決這個(gè)問(wèn)題：給定一美分的美分價(jià)值（例如200 = 2美元，1000 = 10美元），找到構(gòu)成美元價(jià)值的所有硬幣組合。只有便士（1￠），鎳（5￠），角錢（10￠）和四分之一（25￠）。例如，如果給出100，答案應(yīng)該是：4 quarter(s) 0 dime(s) 0 nickel(s) 0 pennies 3 quarter(s) 1 dime(s) 0 nickel(s) 15 pennies etc.我相信這可以通過(guò)迭代和遞歸方式解決。我的遞歸解決方案非常錯(cuò)誤，我想知道其他人如何解決這個(gè)問(wèn)題。這個(gè)問(wèn)題的難點(diǎn)在于盡可能提高效率。

查看完整描述

3 回答

FFIVE

TA貢獻(xiàn)1797條經(jīng)驗(yàn) 獲得超6個(gè)贊

我很久以前就研究了這個(gè)問(wèn)題，你可以讀一下我的小文章。這是Mathematica的來(lái)源。

通過(guò)使用生成函數(shù)，您可以獲得問(wèn)題的封閉形式的恒定時(shí)間解決方案。格雷厄姆，克努特和帕塔什尼克的混凝土數(shù)學(xué)就是這本書的書，并且對(duì)這個(gè)問(wèn)題進(jìn)行了相當(dāng)廣泛的討論?；旧?，您定義了一個(gè)多項(xiàng)式，其中第n個(gè)系數(shù)是以n美元進(jìn)行更改的方式的數(shù)量。

這篇文章的第4-5頁(yè)顯示了如何使用Mathematica（或任何其他方便的計(jì)算機(jī)代數(shù)系統(tǒng)）在三行代碼中在幾秒內(nèi)計(jì)算10 ^ 10 ^ 6美元的答案。

（而且這已經(jīng)很久以前在75Mhz Pentium上只有幾秒鐘......）

反對(duì) 回復(fù) 2019-08-29

DIEA

TA貢獻(xiàn)1820條經(jīng)驗(yàn) 獲得超2個(gè)贊

注意：這僅顯示方式的數(shù)量。

Scala功能：

def countChange(money: Int, coins: List[Int]): Int =
  if (money == 0) 1
  else if (coins.isEmpty || money < 0) 0
  else countChange(money - coins.head, coins) + countChange(money, coins.tail)

反對(duì) 回復(fù) 2019-08-29

幕布斯6054654

TA貢獻(xiàn)1876條經(jīng)驗(yàn) 獲得超7個(gè)贊

我贊成遞歸解決方案。你有一些面額列表，如果最小的面額可以平均分配任何剩余的貨幣金額，這應(yīng)該工作正常。

基本上，您從最大面額移動(dòng)到最小面額。
遞歸，

您有一個(gè)當(dāng)前總數(shù)要填充，以及一個(gè)最大面額（剩下超過(guò)1個(gè)）。如果只剩下1個(gè)面額，那么只有一種方法可以填補(bǔ)總數(shù)。您可以使用當(dāng)前面額的0到k個(gè)副本，使得k * cur面額<=總計(jì)。
對(duì)于0到k，使用修改的總計(jì)和新的最大面額調(diào)用函數(shù)。
將結(jié)果從0添加到k。這就是你可以用多少種方式從目前的面額中填補(bǔ)總數(shù)。返回此號(hào)碼。

這是我所說(shuō)的問(wèn)題的python版本，200美分。我得到了1463種方式。此版本打印所有組合和最終計(jì)數(shù)總數(shù)。

#!/usr/bin/python# find the number of ways to reach a total with the given number of combinationscents = 200denominations = [25, 10, 5, 1]names = {25: "quarter(s)", 10: "dime(s)", 5 : "nickel(s)", 1 : "pennies"}def count_combs(left, i, comb, add):
    if add: comb.append(add)
    if left == 0 or (i+1) == len(denominations):
        if (i+1) == len(denominations) and left > 0:
           if left % denominations[i]:
               return 0
           comb.append( (left/denominations[i], demoninations[i]) )
           i += 1
        while i < len(denominations):
            comb.append( (0, denominations[i]) )
            i += 1
        print(" ".join("%d %s" % (n,names[c]) for (n,c) in comb))
        return 1
    cur = denominations[i]
    return sum(count_combs(left-x*cur, i+1, comb[:], (x,cur)) for x in range(0, int(left/cur)+1))count_combs(cents, 0, [], None)

反對(duì) 回復(fù) 2019-08-29