読者です 読者をやめる 読者になる 読者になる

両替問題の解答

先日闇雲に両替問題だけ書きましたが、
両替問題の解答プログラムを示してみます。


まず、n円を a円、b円、c円の硬貨に両替する方法が
何通りあるかを返す関数を f(n, [a, b, c]) と定義します。


すると、擬似コードで

f(n, [a, b, c]) = n円を[b, c]で表す方法
      + (n-a)円を[b,c]で表す方法
      + (n-2a)円を[b,c]で表す方法
      + ...

と書けますので、そのまま実装するとPythonでのコードは以下のようになります。

def f(n, currency=[10000,5000,2000,1000,500,100,50,10,5,1]):
    currency.sort()
    currency = currency[::-1]
    
    if len(currency) == 1:
        if n % currency[0] == 0:
            return 1
        return 0
    
    cnt = 0
    for i in xrange(n / currency[0] + 1):
        cnt += f(n - i * currency[0], currency[1:])
    return cnt

しかしこのままでは速度が遅すぎて、
f(2000)を計算するだけでも 8.453 [sec] もかかってしまいます。
そこで高速化を試みます。


上記のプログラムが遅い原因は、
関数 f が呼び出される回数を考えればわかります。
例えば f(30, [10, 5, 1]) を考えてみます。
すると、

f(30, [10, 5, 1])
  f(30, [5, 1])
    f(30, [1])
    f(25, [1])
    f(20, [1])
    f(15, [1])
    f(10, [1])
    f(5, [1])
    f(0, [1])
  f(20, [5, 1])
    f(20, [1])
    f(15, [1])
    f(10, [1])
    f(5, [1])
    f(0, [1])
  f(10, [5, 1])
    f(10, [1])
    f(5, [1])
    f(0, [1])
  f(0, [5, 1])
    f(0, [1])

という呼び出しがあり、f(10, [1])が3回呼び出されているのがわかります。
実際、f(10000, [10000, 5000, 2000, ... , 5, 1]) を呼び出すと、
f(100, [10, 5, 1])が100回呼び出されます。


そこで、関数のmemoize化を簡単に行ってみます。

cache = {}
def f(n, currency=[10000,5000,2000,1000,500,100,50,10,5,1]):
    currency.sort()
    currency = currency[::-1]
    
    if cache.has_key((n, len(currency))):
        return cache[(n, len(currency))]
    if len(currency) == 1:
        cache[(n, len(currency))] = 1
        return 1
    cnt = 0
    for i in xrange(n / currency[0] + 1):
        cnt += f(n - i * currency[0], currency[1:])
    cache[(n, len(currency))] = cnt
    return cnt


すると f(2000) は 0.188 [sec] で計算でき、
さらに目的の f(10000) を 4.640 [sec] で計算することができました。
答えは

24,597,373,439 (245億9737万3439)

となります。


これで目的は達成できたわけですが、
f(20000) の計算に 17.703 [sec] もかかってしまいますので、
もう少し遊び心で高速化してみます。

f(5n, [5, 1]) = f(5n, [1]) + f(5n - 5, [1]) + f(5n - 10, [1]) + ...
    = n + 1

であることを利用し、

cache = {}
def f(n, currency=[10000,5000,2000,1000,500,100,50,10,5,1]):
    if cache.has_key((n, len(currency))):
        return cache[(n, len(currency))]
    if len(currency) == 2:
        x = n / currency[0]
        ret = x + 1
        cache[(n, len(currency))] = ret
        return ret
    elif len(currency) == 1:
        cache[(n, len(currency))] = 1
        return 1
    cnt = 0
    for i in xrange(n / currency[0] + 1):
        cnt += f(n - i * currency[0], currency[1:])
    cache[(n, len(currency))] = cnt
    return cnt

などとしてみると、f(10000)が 0.312 [sec] で計算できるようになりました。
f(20000) は 1.468 [sec] で計算できました。
これは使用可能な通貨の中に1円硬貨が存在する場合にのみ有効で、
かつ第2引数が降順でソートされていなければならないという高速化です。


さらに

f(10n, [10, 5, 1]) = f(10n, [5, 1])
            + f(10n - 10, [5, 1])
            + f(10n - 20, [5, 1])
            + ...
    = (2n + 1) + {2(n - 1) + 1} + {2(n - 2) + 1} + ...
    = (n + 1) ** 2

であることを利用し、

cache = {}
def f(n, currency=[10000,5000,2000,1000,500,100,50,10,5,1]):
    if cache.has_key((n, len(currency))):
        return cache[(n, len(currency))]
    if len(currency) == 3:
        if n % currency[0] == 0:
            x = n / currency[0]
            ret = (x + 1) ** 2
            cache[(n, len(currency))] = ret
            return ret
    elif len(currency) == 2:
        x = n / currency[0]
        ret = x + 1
        cache[(n, len(currency))] = ret
        return ret
    elif len(currency) == 1:
        cache[(n, len(currency))] = 1
        return 1
    cnt = 0
    for i in xrange(n / currency[0] + 1):
        cnt += f(n - i * currency[0], currency[1:])
    cache[(n, len(currency))] = cnt
    return cnt

これで f(10000) が 0.047 [sec] で計算できるようになりました。
この高速化はnが10の倍数のケースでしか有効ではありませんが、
f(100000) が 3.406 [sec] で求められるようになりました。

もはやこれ以上の高速化は不要ですが、
もう少し遊んで高速化してみます。


先程までの高速化と同様に、

f(50n, [50, 10, 5, 1]) = f(50n, [10, 5, 1])
              + f(50n - 50, [10, 5, 1])
              + f(50n - 100, [10, 5, 1])
              + ...
    = (n + 1) * (5n(10n + 11) + 6) / 6
f(100n, [100, 50, 10, 5, 1]) = f(100n, [50, 10, 5, 1])
              + f(100n - 100, [50, 10, 5, 1])
              + ...
    = (n + 1) * (n * (n * (100n + 240) + 131) + 6) / 6

であることを利用し、

cache = {}
def f(n, currency=[10000,5000,2000,1000,500,100,50,10,5,1]):
    if cache.has_key((n, len(currency))):
        return cache[(n, len(currency))]
    if len(currency) == 5:
        if n % currency[0] == 0:
            x = n / currency[0]
            ret = (x + 1) * (x * (x * (100 * x + 240) + 131) + 6) / 6
            cache[(n, len(currency))] = ret
            return ret
    elif len(currency) == 4:
        if n % currency[0] == 0:
            x = n / currency[0]
            ret = (x + 1) * (5 * x * (10 * x + 11) + 6) / 6
            cache[(n, len(currency))] = ret
            return ret
    elif len(currency) == 3:
        if n % currency[0] == 0:
            x = n / currency[0]
            ret = (x + 1) ** 2
            cache[(n, len(currency))] = ret
            return ret
    elif len(currency) == 2:
        x = n / currency[0]
        ret = x + 1
        cache[(n, len(currency))] = ret
        return ret
    elif len(currency) == 1:
        cache[(n, len(currency))] = 1
        return 1
    cnt = 0
    for i in xrange(n / currency[0] + 1):
        cnt += f(n - i * currency[0], currency[1:])
    cache[(n, len(currency))] = cnt
    return cnt

としてみると、f(100000) が 0.047 [sec] で計算できるようになり、
また f(1000000) は 4.454 [sec] で求めることができました。

f(100000) = 476,320,696,371,372,721
(47京6320兆6963億7137万2721)
f(1000000) = 239,595,332,030,985,082,915,281,201
(239☆5953垓3203京0985兆0829億1528万1201)

※ ☆の箇所は「ジョ」という単位なのですが、変換できませんでした。

こんなところでしょうか。
他の面白い・高速な解法などがあれば
是非教えていただけるとうれしいです。