選び方と問題の分け方を比べる
貪欲法は、その時点で良さそうな選択を決め、原則として後から取り消さずに解を組み立てます。動的計画法(DP)は、状態で表した部分問題の答えを保存し、それらを組み合わせます。前者が常に雑で、後者が常に正しいという違いではありません。どちらにも、問題の目的と制約に合う正当性の説明が必要です。特に貪欲法では、局所的な選択を含む最適解が存在することなどを示さなければ、目先の利点から全体の最適性へ進めません。DPでも、必要な情報を欠いた状態や誤った遷移を使えば正しい解は得られません。
| 観点 | 貪欲法 | 動的計画法 |
|---|---|---|
| 構成 | 局所的な選択を確定 | 部分問題の解を再利用 |
| 必要な根拠 | 選択してよいことの証明 | 状態と遷移の正当性 |
| 注意点 | 任意の硬貨では最大優先が失敗 | 状態数が大きいと計算が重い |
硬貨の枚数を減らす反例
硬貨の額面が1、3、4で、合計6を最小枚数で作る問題を考えます。最大の硬貨から選ぶ貪欲法は4を選び、残り2を1+1で作るので3枚です。一方、3+3なら2枚で済みます。この一例で、任意の額面に最大硬貨優先を使う一般的な主張は否定できます。ただし、あらゆる硬貨体系で貪欲法が失敗することを示したわけではありません。特定の額面集合では最適になる場合があり、その条件を別に証明します。現実によく使う硬貨でうまくいく経験を、任意の数値の組へ広げないことが大切です。
DPは最後の一枚から状態を定める
作る金額xに対する最小枚数をdp[x]とし、dp[0]=0とします。最後に使う硬貨cを一つ選べば、その前はx−cを作ればよいので、可能なcについてdp[x−c]+1の最小値を取ります。1、3、4の例では、dp[6]はdp[5]+1、dp[3]+1、dp[2]+1の最小です。ここでは同じ額面を何回でも使えて、金額が非負整数であると仮定しています。使える硬貨枚数に上限があるなら、残り枚数など追加の状態や異なる更新順序が必要です。似た漸化式でも、問題の制約が変わるとそのまま使えるとは限りません。
coins, target = [1, 3, 4], 6
inf = target + 1
dp = [0] + [inf] * target
for amount in range(1, target + 1):
for coin in coins:
if coin <= amount and dp[amount - coin] != inf:
dp[amount] = min(dp[amount], dp[amount - coin] + 1)
assert dp[6] == 2
remaining, used = target, 0
for coin in sorted(coins, reverse=True):
used += remaining // coin
remaining %= coin
assert remaining == 0 and used == 3
到達不能と解の復元も設計する
額面が3と4だけなら、金額1や2は作れません。到達不能を0枚と同じ値で持つと、そこへ一枚足した誤った解を作ってしまいます。無限大などで区別し、有効な前状態からだけ更新します。最小枚数だけでなく硬貨の内訳も欲しいなら、改善したときの最後の硬貨を記録し、金額を減らしながら戻ります。同枚数の解が複数ある場合にどれを選ぶかも別の仕様です。貪欲法でもDPでも、目的値だけが出ればAPI全体が完成するわけではなく、存在しない解や結果の説明まで含めて扱う必要があります。
状態数と数値の大きさを評価する
額面数をk、目標金額をAとすると、このDPは典型的にO(kA)時間、O(A)領域です。Aという数値に比例することと、Aを二進数で記述する入力長に比例することは違います。非常に大きい金額では表を持てないため、状態削減や別の数理的性質が必要になる場合があります。貪欲法が正しいと証明できれば、より小さい費用で済むこともあります。選択は「まずDPなら安全」ではなく、目的、局所選択の根拠、状態に必要な情報、状態数の順に考えます。小さな全列挙で最適値と比較することも、誤った貪欲規則や遷移を見つける有効な検査です。大きな金額では、この数値への依存が実装上の制約になります。