ネタ元: 「お手本になるようなソースコード」(1) @ITクラブ Cafe − @IT 第一引数が0以上の整数であれば、 その表す金額を日本円で現金化したときに、 その枚数が最小となる紙幣と硬貨の組み合わせを、 標準出力に出力するコンソールアプリケーションを作ってください。 例)1625⇒1000*1+500*1+100*1+10*2+5*1 例のような、扱うお金が全部一つ下お金の倍数になっているなら、大きなお金から順に商をとっていくだけでよいので簡単です。しかし、8000円札のような任意のお金を使えるようにすると、急に複雑になります。これは、いわゆる「ナップサック問題」といわれる問題の仲間で、NP困難であることが知られています。 ナップサック問題を解くには「動的計画法」を用いるのが一般的なようなので、このページを参考にして、ruby で作ってみました。 スレに投稿したコード(動的計画法で