最小お釣問題について考える


###いかにしてお釣を最小に抑えるか

財布の中がこんな状況だったとする。

```
1,000　円札:1枚
100　　円玉:3枚
10　　 円玉:1枚
1　　　円玉:1枚
```

この財布を持ってコンビニで

```
価格:756円
```

の商品を買うとき、どのような支払い方をすれば
もっともお釣の枚数が少なくて済むだろうか。

面倒くさい時はたぶんこんな払い方をする。

```
1000円札1枚を支払う
↓
1000-756=244円のお釣
↓
2*100
4*10
4*1
↓
合計10枚のお釣を貰う。
```

これではお財布がパンパンだ。
もう少し楽にしてやろう。

```
1000円札1枚を支払う
10円玉1枚を支払う
↓
1010-756= 254円のお釣
↓
1*200
1*50
4*1
↓
合計6枚のお釣を貰う。
```

ちょっとだけ減ったぞ。
もっといけないか？

```
1000円札1枚を支払う
100円玉3枚を支払う
10円玉1枚を支払う
1円玉1枚を支払う
↓
1311円-756=555円のお釣
↓
1*500
1*50
1*5
↓
合計3枚のお釣を貰う。
```

Cool!
1311円という不可解な支払い方をされて店員は困惑することだろう。
「でも突き返す訳にはいかないし…」と半信半疑でレジに打ち込んで、
表示される555円の文字。
これはドヤ顔できる。勝ち誇った顔でお釣りを受け取れる。
おそらく次からマッハGOというアダ名で呼ばれるに違いない。

###プログラムに落としこんでみよう
今回はうまくいったものの、ちょっとでも計算を間違えればただの変な人だ。
頭を使わず店員にドヤ顔するために、これをプログラムに落としこむことを
検討してみたい。どうやったら実現できるだろうか。

以下のような手順で総当りをしてみるのはどうだろう。

1. 財布の中のお金の組み合わせを全部列挙する。
2. その中で支払額が請求額を超えているものだけを取り出す。
3. 残った全部の組み合わせに対し、それぞれのお釣の数を計算する。
4. もっともお釣が少なかったものを選ぶ。


総当り・・・美しくない。でもとりあえず実現することを優先だ。
それがこちら。

```py:smart_pay.py
# -*- coding: utf-8 -*-
import itertools
money_type = (10000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1)

def smart_pay(saifu,kakaku):
    bestPttern=None
    patterns=[]
    for mtype in money_type:
        pattern=[]
        for c in range(saifu[mtype]+1):
            pattern.append([mtype,c])
        if len(pattern)>1:
            patterns.append(pattern)
    for p in itertools.product(*patterns):
        ptn={x[0]:x[1] for x in p}
        if coins2price(ptn)>=kakaku:
            if  bestPttern is None:
                bestPttern=ptn
            else:
                if count_coins(price2coins(coins2price(bestPttern)-kakaku)) > count_coins(price2coins(coins2price(ptn)-kakaku)):
                    bestPttern=ptn
    return bestPttern

def price2coins(price):
    coins = {}
    for mt in money_type:
        coins[mt], price = divmod(price, mt)
    return coins

def coins2price(coins):
    return sum(key * val for key,val in coins.items())

def count_coins(coins):
    return sum(val for key,val in coins.items())

if __name__ == "__main__":
    saifu={}
    print("まずお財布の中身をお聞きします...")
    for mtype in money_type:
        saifu[mtype]= int(raw_input(str(mtype)+ "円は何枚？\n>"))
    kakaku=int(raw_input("いくらの商品を買いますか？\n>"))
    print("最適な支払い方法は.\n.\n.\n")
    bestPttern=smart_pay(saifu,kakaku)
    if bestPttern is None:
        print("おかねたりないです。。。")
    else:
        for key,val in bestPttern.items():
            print(str(key)+"円を"+str(val)+"枚")
        print("です！")
```

メソッドの機能はこんな感じ。

* price2coins:金額を入れると貨幣の(理想的な)枚数を教えてくれる。
* coins2price:貨幣を入れると金額を教えてくれる。
* count_coins:貨幣の数を数えてくれる。
* smart_pay:財布の中身と購入額を入れると最良な支払い方法を教えてくれる。

早速実行してみる。

```実行結果
まずお財布の中身をお聞きします...
10000円は何枚？
>0
5000円は何枚？
>0
2000円は何枚？
>0
1000円は何枚？
>1
500円は何枚？
>0
100円は何枚？
>3
50円は何枚？
>0
10円は何枚？
>1
5円は何枚？
>0
1円は何枚？
>1
いくらの商品を買いますか？
>756
最適な支払い方法は.
.
.

1000円を1枚
1円を1枚
10円を1枚
100円を3枚
です！

```

素晴らしい。
これで思う存分コンビニでドヤ顔できる。

###ちょっとした解説

###### coins[mt], price = divmod(price, mt)
priceをmt(貨幣の額面)で割った金額とあまりを同時に取得してる。
Pythonすごい。

######return sum(key * val for key,val in coins.items())
coinsというDictionary(key:貨幣の額面,value:貨幣の枚数)から
forループでKeyValueを取り出し掛け算して配列にしたのをSUMってる。
Pythonすごい。

######for p in itertools.product(*patterns):
[500,2]や[100:3]といった貨幣の枚数を保存した配列を保存した配列を
itertools.productに渡して、総当りの組み合わせをforループで受け取ってる。
Pythonすごい。

###まとめ
Pythonすごい。