Pythonで硬貨の問題

ある値段を払うのに何枚のコインが必要かとか、そういう問題。
お金がたりない、組み合わせた結果ちょうどの値段にならないとかは考慮してない。

# coding=utf-8

def solve(coins, price):
    """
    Arguments
        coins:    硬貨の価格と枚数の辞書
        price:    算出したい値段
    """
    total_coin_count = 0

    used_coins = []

    # 硬貨の価格を高い順に並べたリストを得る
    coin_values = coins.keys()
    coin_values.sort()
    coin_values.reverse()

    # 高い順に使用する枚数を得る
    for coin_value  in coin_values:
        use_coin_count = min(price / coin_value, coins[coin_value])
        price -= use_coin_count * coin_value
        total_coin_count += use_coin_count
        used_coins.append((coin_value, use_coin_count))

    return total_coin_count, dict(used_coins)


coins = {
    1: 3,
    5: 1,
    10: 9,
    50: 2,
    100: 8,
    500: 1
}
total_coin_count, used_coin = solve(coins, 1000)
print "全部で%s枚の硬貨を使用" % total_coin_count
for k, v in used_coin.iteritems():
    if v:
        print "%s円玉を%s枚使用" % (k ,v)

実行結果

全部で6枚の硬貨を使用
100円玉を5枚使用
500円玉を1枚使用