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枚使用