いかにしてお釣を最小に抑えるか
財布の中がこんな状況だったとする。
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というアダ名で呼ばれるに違いない。
プログラムに落としこんでみよう
今回はうまくいったものの、ちょっとでも計算を間違えればただの変な人だ。
頭を使わず店員にドヤ顔するために、これをプログラムに落としこむことを
検討してみたい。どうやったら実現できるだろうか。
以下のような手順で総当りをしてみるのはどうだろう。
- 財布の中のお金の組み合わせを全部列挙する。
- その中で支払額が請求額を超えているものだけを取り出す。
- 残った全部の組み合わせに対し、それぞれのお釣の数を計算する。
- もっともお釣が少なかったものを選ぶ。
総当り・・・美しくない。でもとりあえず実現することを優先だ。
それがこちら。
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すごい。