貪欲法が最適でない場合の判定

硬貨問題などで貪欲法の結果 $G (n)$ と動的計画法による最適値 $O (n)$ を比べ、 $G (n) > O (n)$ となる $n$ を見つけたり数えたりできる

前提

動的計画法の基本（硬貨の最小枚数）（大学数学アルゴリズムと計算量）

説明

硬貨の種類が決まっているとき、「払える最大の硬貨から使う」貪欲法の枚数 $G (n)$ と、動的計画法で求めた本当の最小枚数 $O (n)$ を表にして並べます。そうすることで、貪欲法が損をする金額 $n$ （ $G (n) > O (n)$ となる $n$ ）を見つけたり数えたりできます。新しい硬貨の組を作るときや、プログラムで貪欲法を使ってよいかを確かめるときに役立ちます。ここでは、1 円硬貨を含み、どの金額も払える硬貨の組を考えます。

なぜそうしてよいのか

貪欲法の払い方も、 $n$ 円をちょうど払う払い方の 1 つです。 $O (n)$ はそのような払い方すべての中での最小枚数なので、いつでも $G (n) \geq O (n)$ が成り立ちます。したがって「貪欲法が最適でない」とは、 $G (n) > O (n)$ と真に大きくなることです。両者を同じ $n$ で比べれば判定できます。

$O (n)$ は前提の技能の漸化式 $O (n) = min_{c \leq n} {O (n - c) + 1}$ で求めます。 $G (n)$ も同じ形の漸化式で表せます。貪欲法は最初に「 $n$ 以下で最大の硬貨 $c^{*} (n)$ 」を 1 枚使い、残り $n - c^{*} (n)$ 円にも同じ規則を当てはめます。よって $G (n) = G (n - c^{*} (n)) + 1$ です。 $O$ は可能な硬貨をすべて試して最小を取りますが、 $G$ は 1 通りしか試しません。この違いが差を生みます。

差が出ても、それより大きい金額すべてで差が出るとは限りません。そのため、調べる範囲の $n$ をひとつずつ比べる必要があります。

手順

動的計画法で $O$ の表を作る： $O (0) = 0$ 、 $m = 1, 2, \dots$ について $O (m) = min_{c \leq m} {O (m - c) + 1}$ （ $c$ は硬貨の額面で、 $m - c \geq 0$ のものだけを考える）
貪欲法で $G$ の表を作る： $G (0) = 0$ 、 $c^{*} (m)$ を $m$ 以下で最大の硬貨として $G (m) = G (m - c^{*} (m)) + 1$
同じ $m$ で $G (m)$ と $O (m)$ を比べ、 $G (m) > O (m)$ となる $m$ に印を付ける（ $G (m) < O (m)$ となることはないので、出たら計算ミス）
印の付いた $m$ を、問われた形（すべて・個数・最小のもの）で答える

例題

1 円、3 円、4 円の 3 種類の硬貨が何枚でも使えるとする。 $n$ 円をちょうど払うとき、貪欲法の枚数を $G (n)$ 、最小枚数を $O (n)$ とする。 $1 \leq n \leq 12$ の範囲で $G (n) > O (n)$ となる $n$ をすべて求めよ。

例題の解答

手順1（ $O$ の表）： $O (0) = 0$ から順に、 $O (m) = min {O (m - 1), O (m - 3), O (m - 4)} + 1$ を計算する（引けるものだけを使う）。 $O (1) = 1, O (2) = 2, O (3) = 1, O (4) = 1, O (5) = 2, O (6) = min {2, 1, 2} + 1 = 2, O (7) = 2, O (8) = 2, O (9) = 3, O (10) = min {3, 2, 2} + 1 = 3, O (11) = 3, O (12) = 3$ 。

手順2（ $G$ の表）： $c^{*} (m)$ は $m \geq 4$ なら 4、 $m = 3$ なら 3、 $m \leq 2$ なら 1 である。 $G (1) = 1, G (2) = 2, G (3) = 1, G (4) = 1, G (5) = G (1) + 1 = 2, G (6) = G (2) + 1 = 3, G (7) = G (3) + 1 = 2, G (8) = G (4) + 1 = 2, G (9) = G (5) + 1 = 3, G (10) = G (6) + 1 = 4, G (11) = G (7) + 1 = 3, G (12) = G (8) + 1 = 3$ 。

手順3（比較）： $G (6) = 3 > 2 = O (6)$ である。実際、貪欲法は $4 + 1 + 1$ だが、最適は $3 + 3$ である。 $G (10) = 4 > 3 = O (10)$ である。貪欲法は $4 + 4 + 1 + 1$ だが、最適は $4 + 3 + 3$ である。ほかの $n$ ではすべて $G (n) = O (n)$ となる。

手順4：求める $n$ は $6, 10$ である。

答え: ${6, 10}$

よくある誤り

貪欲法で、残りの金額を超える硬貨まで「最大の硬貨」として選んでしまう誤り。正しくは $m$ 以下で最大の硬貨 $c^{*} (m)$ を選ぶ（例：硬貨 ${1, 3, 4}$ で $m = 3$ なら $c^{*} (3) = 3$ であり、4 ではない）。
一度 $G (n) > O (n)$ となったら、それより大きい $n$ ではずっと貪欲法が失敗すると思い込む誤り。正しくは $n$ ごとに比べる（例：硬貨 ${1, 3, 4}$ では $G (6) > O (6)$ だが、 $G (7) = O (7) = 2$ である）。
$O$ の漸化式で、 $m - c < 0$ となる硬貨も使ったり、 $O (0) = 0$ を置き忘れたりする誤り。正しくは $O (0) = 0$ とし、 $c \leq m$ の硬貨だけで $min$ を取る。
小さい $n$ でいくつか試して差が出なかったので、「貪欲法は常に最適」と結論してしまう誤り。正しくは、問われた範囲のすべての $n$ で $G (n)$ と $O (n)$ を比べる（例：硬貨 ${1, 3, 4}$ では $n \leq 5$ で差がなく、 $n = 6$ で初めて差が出る）。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

貪欲法が最適でない場合の判定

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題