最小お釣問題について考える ref: http://qiita.com/kurehajime/items/243907cef90eb6766110

file0.txt

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

file1.txt

価格:756円

file2.txt

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

file3.txt

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

file4.txt

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

file6.txt

まずお財布の中身をお聞きします...
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枚
です！

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("です！")