データ構造とアルゴリズム
1円、4円、6円の3種類の硬貨で8円を支払う。大きい硬貨から使えるだけ使う貪欲法で決めたときの枚数と、最少の枚数の関係として正しいものはどれか。
- A貪欲法でも最少の2枚になる
- B貪欲法では3枚になり、最少の2枚にならない
- C貪欲法では3枚になり、これが最少である
答えと解説を見る
正解：B. 貪欲法では3枚になり、最少の2枚にならない
貪欲法では、まず6円を1枚使い、残り2円を1円2枚で払うので3枚です。しかし、4円を2枚使えば2枚で払えます。このように貪欲法は、その時点で最もよい選択を積み重ねるだけなので、硬貨の組み合わせによっては最適になりません。動的計画法で「0円から8円までの各金額を払う最少枚数」を小さい金額から順に表にすれば、必ず最少の枚数が求まります。なお、1、5、10、50、100、500円のような日本の硬貨の組み合わせでは、貪欲法でも常に最少になります。
- A. 貪欲法は最初に6円を選ぶので、4円2枚の組み合わせにはたどり着きません。
- B. 正しい。貪欲法は6 + 1 + 1の3枚、最少は4 + 4の2枚です。
- C. 4円2枚なら2枚で払えるので、3枚は最少ではありません。