めもめも〜

なんとなく考えた謎アルゴリズムがそこそこの成果を挙げている。ときどき出てくる謎の誤差*1を修正して、もう少し最適化していけばいいような気がする。判定の優先順位は(枚数)＞(時間)らしいので、枚数を削って行きたいのだけど、速いにこしたことはないし。
1,3000,3001,3002,3003,3004,3005,3006,3007,3008円で6018999円が3006*2002+1*987で2989枚。これで一秒程度なのだけど、もっと削れるだろうか？
(追記)Jの謎アルゴリズムの特徴

• 総当りを大雑把にやってるだけ
• すぐに安い硬貨に頼ろうとする
• まぁ遅くはないんじゃないか

一応この方式でできるところまで最適化したのだけど、結局、上の問題は3006+3003*4+3000*2001+1*981の2987枚どまりでした。当然問題にもよるのだけど、やはり安いコインにむやみに崩すだけではだめそうです。てかこれ、露骨に上方向に最適化可能じゃん。
疲れたのでここらであきらめるか。動的計画法がよくわからない(あまり調べてもいないけれど)・・・

*1:あまりにも綺麗すぎるから、たぶん単純なミスだろう