JAVAのプログランミング

質問

JAVAのプログラミングについて教えてください。
1,10,25,32円の4種のコインを好きな枚数使ってよい場合、ある金額を最少枚数のコインを用いて支払いたい。高速に動くプログラムを再帰関数を用いずに作れ。1234567円を払うには何枚のコインが必要かを出力せよ。

回答No.3

osu_neko09 · ベストアンサー

＞#2
いえ、それはまずいです。818円だと
800円（32円25枚）+18円（10円+1円8枚）合計34枚よりも、
768円（32円24枚）+50円（25円2枚）合計26枚のほうが少なくなります。

なので愚直に32円硬貨が0枚のとき、1枚のとき・・・、おのおのについて25円硬貨が0枚のとき、1枚のとき・・・、と計算するしかないのでは。

が、1,234,567円を支払うとき、32円硬貨が0枚～38580枚を調べるのは遅すぎます。
さて、32円硬貨83枚と1円硬貨24枚で、107枚2680円になりますが、25円硬貨107枚では2675円しかありません。よって、32円硬貨は38580枚から、83枚を引いた38497枚まで調べれば十分です。
また、25円硬貨6枚と1円硬貨9枚で15枚159円ですが、10円硬貨15枚では150円しかありません。よって25円硬貨は（最大枚数）～（最大枚数-6枚）を調べれば十分です。

＃32円硬貨の枚数はもっと狭い範囲で十分のはずなのですが、証明できない。

お礼

ありがとうございます。効率のめちゃくちゃ悪いプログラムは組めました。が、とても１２３４５６７円の計算は....(>_<)

回答No.4

Tacosan

あ～, 本当だ....＞#3. ご指摘ありがとうございます.
一応「ある程度以上は 32円硬貨を使い, 余った分を残りも混ぜる」ということになるんだけど, どこに境界があるんだろう.
この問題のセオリーは DP なんだけど, Java だと DP がやりにくいんだよね～. まあ, こんな問題で再帰使ったらどう考えても「高速」にはなりえないんだけど.

お礼

ありがとうございます。効率のめちゃくちゃ悪いプログラムは組めました。が、とても１２３４５６７円の計算は....(>_<)

回答No.2

Tacosan

1つのアイデアとして:
800円単位では自明だから, 0円～799円までは手計算で答えを求めておく. で, 「800円単位」とそれ以下にわけてそれぞれの必要枚数を調べ和を返す.
「最速」とはいわんが,「高速に動作するプログラム」であることは保証する.

回答No.1

buriburi3

( ´・ω・｀)つ【金種表】
http://www.accessclub.jp/samplefile/samplefile_94.htm

お礼

ありがとうございます。この問題の場合、金種表とは少し違うんです（たとえば５１円のとき　２５円２枚と１円１枚のほうが３２円を使うよりも少ないんです）　でも参考になりました。