日刊 あおのうま Vol.2402（2017.10.29）【頭の体操的な】

お預かり金額 と 釣り銭

お預かり金額(deposit)と値段(price)を与えると、最小枚数の釣り銭構成を返すプログラム。

def change_pattern(deposit, price)
  return [0] if deposit == price
  fail if deposit < price
  
  currencies = [1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 100000]  # 2000円札は嫌がられるので使わない
  change = deposit - price
  max_count = change / currencies.min

  (1..max_count).map{ |count|
    currencies.repeated_combination(count).map{ |pattern|
      return pattern if pattern.inject(:+) == change
    }
  }
end

p change_pattern(1000, 541)

重複あり組合せを探索木にして、少ない枚数組合せから順に取り出しながら、金額一致まで幅優先探索しています。
割り算と再帰で書くのが定番ですが、何となく幅優先探索で書いてみたかったので。

重複あり組合せをどう作ろうかと悩んでいたのですが、標準関数にrepeated_combination があって助かりました。
Ruby べんり。