動的計画法で金種計算
ネタ元: 「お手本になるようなソースコード」（1） ＠ITクラブ Cafe − ＠IT
第一引数が0以上の整数であれば、
その表す金額を日本円で現金化したときに、
その枚数が最小となる紙幣と硬貨の組み合わせを、
標準出力に出力するコンソールアプリケーションを作ってください。例）1625⇒1000*1+500*1+100*1+10*2+5*1
例のような、扱うお金が全部一つ下お金の倍数になっているなら、大きなお金から順に商をとっていくだけでよいので簡単です。しかし、8000円札のような任意のお金を使えるようにすると、急に複雑になります。これは、いわゆる「ナップサック問題」といわれる問題の仲間で、NP困難であることが知られています。
ナップサック問題を解くには「動的計画法」を用いるのが一般的なようなので、このページを参考にして、ruby で作ってみました。
上記のスレに投稿したコードは、数万円程度の少ない金額ならすばやく答えが求められるものの、「100億円は1万円札何枚？」のようなある意味すごく簡単な問題が解けなかったりする*1欠点があります。また、ぴったり払えない場合はエラーになってしまうのもいけてないです。
で、その辺をちょっと改善したのをこっちに張っておきます。
ソース
# !ruby # currency.rb class Currency attr_accessor :price, :count def initialize(price, count=0) @price = price @count = count end def inspect to_str end def to_str "￥#{price}" end end def gcd(m, n) n == 0 ? m : m % n == 0 ? n : gcd(n, m % n) end def select_coin(amount) print "￥#{amount} を #{CURRENCIES.inspect} で支払う。 \n" idx = -1 factor = CURRENCIES.find do |coin| idx+=1 amount % coin.price == 0 && CURRENCIES[0..idx].all?{|cc| cc.price % coin.price == 0} end currencies = factor ? CURRENCIES[0..CURRENCIES.index(factor)] : CURRENCIES unit = currencies.inject(amount){|u, c| unit = gcd(u, c.price)} gain = [0] * ((amount/unit) + 1) choice = [nil] * ((amount/unit) + 1) currencies.each do |item| size = item.price/unit price = item.price*10-1 (size..(amount/unit)).each do |i| space = i - size new_value = price + gain[space] if gain[i] < new_value gain[i] = new_value choice[i] = item end end end i = (amount/unit) just = true while i > 0 item = choice[i] if(item) item.count = item.count + 1 i = i - (item.price/unit) else just = false i = i - 1; end end unless just print "ぴったり払えません！\n" currencies.last.count+=1 end sum = 0 asum = 0 score = 0 currencies.each do |item| next if item.count == 0 print("%8d × %d\n" % [item.price, item.count]) sum += item.count asum += item.price*item.count end print "合計 :￥#{asum} #{sum}枚\n" unless(just) print "お釣 :￥#{asum-amount}\n" end end AMOUNT = (ARGV.shift || '46000').to_i COIN_DATA = ARGV.empty? ? [10000, 5000, 1000, 500, 100, 50, 10, 5, 1] : ARGV.map{|i| i.to_i} CURRENCIES = COIN_DATA.sort.reverse.map{|i| Currency.new(i)} select_coin(AMOUNT)
最大公約数などを使って数を小さくしてから計算しています。
ただし、大きな約数がないがない場合（例えば1億、飛んで1円の支払いなど）は相変わらず無力です。これは分割統治法の考えかたを適用すれば解けそうな気がするのですが*2、厳密解を失わずに分割する一般的な条件がわからないのでギブアップ。*3
実行イメージ
>ruby currency.rb 10000 4000 300 20 1
￥10000 を
[￥4000, ￥300, ￥20, ￥1] で支払う。
4000 × 2
300 × 6
20 × 10
合計 :￥10000 18枚
