コイン両替問題を解く

趣味でやっているCheckIOというプログラミングゲームサイトでコイン両替問題が出ていたので解いてみた。この問題は、決まった種類のコインがあったとき、ある目標金額を両替するときに最小となるコインの数を求めるというものだ。
例えば623円をコインで両替するとしてコインの数が最小となる組み合わせは[500,100,50,10,5,1]=[1,1,0,2,0,3]なので7枚ということになる。単純に思いつく解法は、すべてのコインの組み合わせについて合計してみて、目標金額に達した組み合わせのうち要素数が最小となるものを選ぶことである。
目標金額をprice(int型),コインの種類をdenominations(list型)とし、コインの最小数を得る関数を書いてみる。両替できない場合(10円玉だけで3円とか)もあるので、その場合はNoneを返すこととする。

def check(price, denominations):
    combination_list = itertools.product(*[[x for x in range(price//x+1)] for r in denominations])
    sum_list = [sum(combination) for combination in combination_list if sum([a*b for a,b in zip(combination,denominations)])==price]
    s = min(sum_list) if len(sum_list)>0 else None
    return s

これでcheck(123, [1, 5,10, 20])を計算すると9となった。正解である。ちなみにここでitertools.product()は複数の集合の直積集合をiteratorとして得るツールである。これを使って各コインの最悪必要となる数までの全コインの組み合わせを求めている。また"*"は外側のリストから中身を取り出すpythonの演算子であり、例えば*[1,2,3]=1,2,3となって、今回のようにリストの中身を関数の複数の引数に展開したいときに重宝する。付け加えておくとpythonでiteratorは使い捨てオブジェクトなので、print()して覗いただけでも中身が空になってしまい、要注意である。

さてできた、と思ってチェックしてみると、数が大きいときにえらい時間がかかる。check(1234, [1, 5,10, 20])をやってみると30分かかった、123だと0.2秒で終わったのにである。考えてみると、この手順ではコイン毎の最悪必要となる枚数を目標金額//コイン金額としているので、全部1円玉にする場合とか明らかに無駄な計算もやってしまうことになる。コイン毎最悪必要となる枚数をr、コイン種類数をnとすると、処理量はに比例する。

一般的に考えてみると少額コインと高額コインのペアについて、少額コインはペアの最小公倍数となる金額に必要な枚数より多くは不要なように思われる。例えば5円玉と3円玉があったとして、5,10は5円玉だけ、3,6,9,12は3円玉だけでしか作れないが、15以上になると15の倍数分は5円玉を使った方が明らかにコイン枚数は少なくなるので、3円玉は4枚より多くは不要ということになる。なので任意のペアについて探索するコイン数の上限を設定して計算させてみる。

任意の整数(a,b)の最小公倍数はa*b/最大公約数なのでユークリッドの互除法を用いて最大公約数を求めてから最小公倍数を計算する。これを実装したのが関数lcmで、これを使ってcheck関数の１行目でコインごとに、そのコインより高額なコインの金額との最小公倍数を計算して辞書型に落とし込んでいる。さらに２行目でコイン金額で割って枚数に変換したうえで最小限必要となる枚数に変換している。３行目で全組み合わせをリスト化するときに、必要枚数以上の組み合わせはリストしないようにしている。

import itertools

def gcd(a,b):
    big = max(a,b)
    sml = min(a,b)
    while(big%sml!=0):
        bih = big
        big = sml
        sml = bih % sml
    return sml

def lcm(a,b):
    return ( a*b//gcd(a,b))

def check(price, denominations):
    lc = {x:[lcm(x,y) for y in denominations if x<y] for x in denominations}
    md = {x:min(lc[x])//x if len(lc[x])>0 else price//x+1 for x in denominations}
    combination_list = itertools.product(*[[x for x in range(md[r])] for r in denominations])
    sum_list = [sum(combination) for combination in combination_list if sum([a*b for a,b in zip(combination,denominations)])==price]
    s = min(sum_list) if len(sum_list)>0 else None
    return s

再度check(1234, [1, 5,10, 20])をやってみると0.001秒で終わった。