お釣りの札と硬貨の枚数をもとめたいです。Rubyで解きたいのですがやり方がわかりません。

468円の買い物をして1万円札を出したときの実行結果は以下の通りになります。

```

    五千円札の枚数   = 1
    千円札の枚数     = 4
    五百円玉の枚数   = 1
    百円玉の枚数     = 0
    五十円玉の枚数   = 0
    十円玉の枚数     = 3
    五円玉の枚数     = 0
    一円玉の枚数     = 2
    
```
CC BY-SA 4.0
2018-10-15T08:10:13.870
49292
2018-11-09T13:01:03.667
2018-10-16T09:52:31.837
3054
30525
question
ruby アルゴリズム
お釣りの札と硬貨の枚数をもとめたい
「用意された種類のお金を組み合わせて x 円払いたい。お金の枚数を最小にしつつ払うにはどれを何枚払えば良いだろうか？」という問題を解くことを考えます
(どんな枚数でも良いのなら、1 円玉をたくさん払えば良くなってしまいます)。

ご提示のような種類のお金の場合、これは貪欲法で求めることができます。つまり、額面の大きな種類のお金で払えるだけ払ってしまい、払えなくなったら次に大きな種類のお金で払うことを考えていけば良いです。これで良いことの証明はここに書くには長いので省略しますが、興味があれば投稿末尾にリンクしたページをご覧ください。

部分的な例として「x 円払うのに、5000 円札で払えるだけ払うと 5000 円札を何枚使って、その後何円残るか」を計算する Ruby
のコードを示しておきます。

```

    $ irb
    irb(main):001:0> x = 9532              # 今払いたいお金が変数 x に代入されているとします。
    => 9532
    irb(main):002:0> n5000 = x / 5000      # 5000 円札何枚まで払えるかは、整数として割り算をすれば分かります。ここでは変数 n5000 に代入してみます。
    => 1
    irb(main):003:0> x = x - 5000 * n5000  # 残金は、上で求めた枚数分の金額を引けば分かります。
    => 4532
    
```

尚、硬貨の種類によっては貪欲法で解けないことがあるので注意してください。より詳細な情報は以下のサイトが参考になるかと思います (「硬貨
貪欲法」などで検索すると出てきます)。

  * [硬貨の問題が貪欲法で解けるための条件](https://qiita.com/s417-lama/items/0cdd95fddb2067876896) \-- Qiita
  * [欲張り法 (greedy strategy)](http://www.geocities.jp/m_hiroi/light/pyalgo22.html) \-- M.Hiroi's Home Page
  * [Change-making problem](https://en.wikipedia.org/wiki/Change-making_problem) \-- 英語版 Wikipedia
CC BY-SA 4.0
2018-10-15T08:40:58.497
49293
2018-10-15T08:59:20.433
2018-10-15T08:59:20.433
19110
19110
49292
answer
考え方のヒントだけ回答してみます(私もソラではRubyを書けないので)。

「お釣りの総額」は(手持ちの)1万円から商品の値段を引けば求められますよね？  
求めた「お釣り」を、大きい額面の紙幣また硬貨で順に割っていきます。

```

    9532 ÷ 5,000 = 1.9064
    
```

少数以下を切り捨てて、整数部分だけ見るとその額面で必要な枚数になります(今回は"1")。  
「5,000円は1枚」と分かったので、元のお釣りから引き算しておきます(残りのお釣りはxxx円)。  
今度は1,000円札が何枚必要かを同じように計算します。  
これをそれぞれの額面で繰り返していけば、それぞれの額面で何枚必要になるかを求められるはずです。
CC BY-SA 4.0
2018-10-15T08:42:13.027
49294
2018-10-15T11:43:12.880
2018-10-15T11:43:12.880
3060
3060
49292
answer
```

    n5000, amari = (10000 - 468).divmod(5000)
    n1000, amari = amari.divmod(1000)
    n500, amari = amari.divmod(500)
    n100, amari = amari.divmod(100)
    n50, amari = amari.divmod(50)
    n10, amari = amari.divmod(10)
    n5, n1 = amari.divmod(5)
    
    puts <<EOS
    五千円札の枚数   = #{n5000}
    千円札の枚数     = #{n1000}
    五百円玉の枚数   = #{n500}
    百円玉の枚数     = #{n100}
    五十円玉の枚数   = #{n50}
    十円玉の枚数     = #{n10}
    五円玉の枚数     = #{n5}
    一円玉の枚数     = #{n1}
    EOS
    
```
CC BY-SA 4.0
2018-11-09T13:01:03.667
50131
2018-11-09T13:01:03.667
30913
49292
answer