コインチェンジ
💡
コインチェンジ問題は、動的計画法（Dynamic Programming）を代表する有名な問題の一つです。貪欲法（Greedy）と動的計画法のアプローチの違いを明確に示しており、貪欲法だけではグローバルな最適解ではなくサブ最適解に陥る可能性があることを示す良い例でもあります。
ある貨幣システムがあり、
n 種類のコインが与えられ、それぞれに正の価値 がついているとします。このとき、合計金額 x をできるだけ少ない枚数のコインで作る方法を見つけてください。たとえば、コインの値が で、必要な金額が
11 の場合、最適解は 1 + 5 + 5 で 3 枚となります。入力
最初の行には、2 つの整数
n (1 ≤ n ≤ 100) と x (1 ≤ x ≤ ) が与えられます。次の行には、
n 個のスペース区切りの整数 (1 ≤ ≤ ) が与えられます。出力
必要な金額
x を作るのに使うコインの最小枚数を出力してください。もし x を作ることができない場合は -1 を出力してください。例
入力 | 出力 |
3 11
1 5 7 | 3 |
3 12
1 5 7 | 2 |
解説
- 11 → 1 + 5 + 5
- 12 → 5 + 7
チュートリアル
常に使える最大のコインを選び続ける貪欲法ではうまくいかないことがあります。最初の例がその典型的な例です。11 を作りたいときに、まず最大のコイン 7 を使うと 11−7=4 が残り、結果として 1 を 4 枚使うことになり、合計 5 枚のコインが必要になってしまいます。しかし実際の最適解は (5 + 5 + 1) で 3 枚です。
そこで、
d[i] を「合計 i を作るのに必要なコインの最小枚数」と定義します。x までのすべての値を正しく更新できれば、最終的な答えは d[x] となります。初期状態として、
d の値をすべて無限大（作れない）に設定し、ただし 0 だけは 0 枚のコインで作れるようにします:c = [...]
x = ...
d = [0] + [float('inf')] * x # d[0] は0、 d[1...x] は無限大とする次に、1 から
x までのそれぞれの値を求めるとき、すべてのコインを試し、(num - ci) を利用して num を作れるかどうかを確認し、答えが良くなるようなら更新します。つまり、1...x の各値について、それになり得るすべての前の状態からコインを使って良い解を探します:for num in range(1, x + 1): # 1～x までを順番に見る
for ci in c: # すべてのコインを試して d[num] を最適化
if num - ci >= 0: # i番目のコインを使って num を作れる場合
d[num] = min(d[num], d[num - ci] + 1)
print(d[x])この
d[num] = min(d[num], d[num - ci] + 1) が問題を解く上で重要なポイントです。各イテレーションで、num - ci を作るために必要なコインの最小枚数に 1 枚足すことで、num への最小枚数が改善できるかどうかを確認しています。すべての値（1～x）についてすべてのコインを試し終われば、答えは単純に
d[x] の値になります。以下にサンプル入力を使ったシミュレーションを示します。
c = [1, 5, 7] と x = 11 の場合
d = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
num = 1(1 を作るのに必要なコイン枚数の更新) ci = 1 ⇒ d[1] = d[0] + 1 = 1 ⇒d = [0, 1, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
num = 2(2 を作るのに必要なコイン枚数の更新) ci = 1 ⇒ d[2] = d[1] + 1 = 2 ⇒d = [0, 1, 2, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
num = 3(3 を作るのに必要なコイン枚数の更新) ci = 1 ⇒ d[3] = d[2] + 1 = 3 ⇒d = [0, 1, 2, 3, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
num = 4(4 を作るのに必要なコイン枚数の更新) ci = 1 ⇒ d[4] = d[3] + 1 = 4 ⇒d = [0, 1, 2, 3, 4, ∞, ∞, ∞, ∞, ∞, ∞, ∞]ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
num = 5(5 を作るのに必要なコイン枚数の更新) ci = 1 ⇒ d[5] = d[4] + 1 = 5 ⇒d = [0, 1, 2, 3, 4, 5, ∞, ∞, ∞, ∞, ∞, ∞]ci = 5 ⇒ d[5] = d[0] + 1 = 1 ⇒d = [0, 1, 2, 3, 4, 1, ∞, ∞, ∞, ∞, ∞, ∞]ci = 7 ⇒ num - ci < 0
num = 6(6 を作るのに必要なコイン枚数の更新) ci = 1 ⇒ d[6] = d[5] + 1 = 2 ⇒d = [0, 1, 2, 3, 4, 1, 2, ∞, ∞, ∞, ∞, ∞]ci = 5 ⇒ 更新なし ci = 7 ⇒ num - ci < 0
num = 7(7 を作るのに必要なコイン枚数の更新) ci = 1 ⇒ d[7] = d[6] + 1 = 3 ⇒d = [0, 1, 2, 3, 4, 1, 2, 3, ∞, ∞, ∞, ∞]ci = 5 ⇒ 更新なし ci = 7 ⇒ d[7] = d[0] + 1 = 1 ⇒d = [0, 1, 2, 3, 4, 1, 2, 1, ∞, ∞, ∞, ∞]
num = 8(8 を作るのに必要なコイン枚数の更新) ci = 1 ⇒ d[8] = d[7] + 1 = 2 ⇒d = [0, 1, 2, 3, 4, 1, 2, 1, 2, ∞, ∞, ∞]ci = 5 ⇒ 更新なし ci = 7 ⇒ 更新なし
num = 9(9 を作るのに必要なコイン枚数の更新) ci = 1 ⇒ d[9] = d[8] + 1 = 3 ⇒d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, ∞, ∞]ci = 5 ⇒ 更新なし ci = 7 ⇒ 更新なし
num = 10(10 を作るのに必要なコイン枚数の更新) ci = 1 ⇒ d[10] = d[9] + 1 = 4 ⇒d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 4, ∞]ci = 5 ⇒ d[10] = d[5] + 1 = 2 ⇒d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 2, ∞]ci = 7 ⇒ 更新なし
num = 11(11 を作るのに必要なコイン枚数の更新) ci = 1 ⇒ d[11] = d[10] + 1 = 3 ⇒d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 2, 3]ci = 5 ⇒ 更新なし ci = 7 ⇒ 更新なし
print(d[11])⇒ 3 を出力
Constraints
Time limit: 2.5 seconds
Memory limit: 512 MB
Output limit: 1 MB