コインの組み合わせ問題

本物のページはこちら→coin-combination

Included page "coin-combination" does not exist (create it now)

複数の硬貨をなるべく少ない枚数組み合わせて目的の金額を表現したい、場合。

  • 大きい方の硬貨からできるだけ多く使う。

という欲張りな方法によって解くことにする。
手持ちが

  • 10円
  • 5円
  • 1円
があります。
これらの硬貨を使って16円を表現しようとすると、
Greedyな方法でも
硬貨の種類 枚数
10円 1
5円 1
1円 1
合計 3枚

という最適解が得られる。
一方、もし

  • 12円
  • 5円
  • 1円
の硬貨だった場合
Greedyな方法では
硬貨の種類 枚数
12円 1
5円 0
1円 4
合計 5枚
となる。これは最適解じゃない。
だって
硬貨の種類 枚数
12円 0
5円 3
1円 1
合計 4枚

の方が枚数が少ない=本当はこっちが最適解。
つまり、必ずしもGreedyな方法で最適解が得られるとは限らないのだ。

サポートサイト Wikidot.com