貪欲法・動的計画法とメモ化
硬貨枚数の最小化を通じて、局所的な選択と部分問題の最適値を学びます。
説明
金額を硬貨で作るとき、毎回使える最大の硬貨を選ぶ方法を考えます。この貪欲法は手順が簡単ですが、硬貨の種類によっては最小枚数になりません。動的計画法では、小さい金額の最小枚数を使って次の金額を求めます。
硬貨1・3・4を何枚でも使える条件で金額6を作ります。貪欲法の結果と、0から6までの最小枚数表を比較します。最後に同じ関係を再帰で計算し、計算済みの答えを再利用するメモ化を試します。
1最大の硬貨から使う
6から最大の4を引くと残り2です。次は1を2枚使います。
from functools import cache; coins = [1, 3, 4]; amount = 6硬貨と目標金額; greedy = [4, 1, 1]最大硬貨を優先した結果; sum(greedy), len(greedy), [3, 3]金額・枚数と別の組合せ4・1・1は3枚ですが、3・3なら2枚です。最初に最大硬貨を選ぶと、その後に1を2枚使う必要があり、全体の最小枚数を逃します。
2金額0の答え
dp[x]を金額xの最小枚数とします。0円なら硬貨は0枚です。他の金額はまだ答えがないので無限大にします。
dp = [0] + [float('inf')] * amount0だけ既知、残り未計算; dp初期表dp[0]=0が計算の起点です。金額xで最後に硬貨cを1枚使うなら、それ以前に必要なのは金額x-cです。候補はdp[x-c]+1になります。
31と2の最小枚数
1と2では硬貨3・4を使えないので、1を足して計算します。
dp[1] = dp[0] + 10に硬貨1を足す; dp[2] = dp[1] + 11に硬貨1を足す; dp更新後の表金額1は1枚、2は2枚です。小さい金額の答えを保存しておくことで、その部分を毎回計算し直さずに済みます。
43では候補を比較
最後の硬貨が1ならdp[2]+1=3枚、3ならdp[0]+1=1枚です。小さい方を選びます。
candidates = [(c, dp[3-c]+1) for c in coins if c <= 3]最後の硬貨ごとの候補; dp[3] = min(n for c, n in candidates)最小枚数を保存; candidates, dp候補と更新表硬貨3を最後に使う1枚が選ばれます。「最大を選ぶ」のではなく、使える全ての最終硬貨について、それ以前の最適値と組み合わせて比較しています。
56まで表を埋める
同じ式で4・5・6を順に計算します。x-cはxより小さいので、参照する答えは既に求まっています。
for x in range(4, amount+1):金額の小さい順
options = [(c, dp[x-c]+1) for c in coins if c <= x]使える最終硬貨を列挙
dp[x] = min(n for c, n in options)最小値を保存
print(x, options, dp[x])金額・候補・採用枚数4は1枚、5は2枚、6は2枚です。6で最後に3を選ぶとdp[3]+1=2、4を選ぶとdp[2]+1=3になります。最適な選択を金額ごとに変えられます。
6答えの硬貨を復元
金額6の最適値を実現する硬貨は3です。残り3でも3を選ぶと0になります。
last = next(c for c in coins if c <= 6 and dp[6] == dp[6-c]+1)最適値を実現する最後の硬貨; remaining = 6-last残額; second = next(c for c in coins if c <= remaining and dp[remaining] == dp[remaining-c]+1)残額の硬貨; dp, [last, second], last+second表と復元した組合せ表の最小値だけでなく、実際の組合せ3・3を復元できました。一般には、金額が0になるまで同じ条件を繰り返すか、表の計算中に選んだ硬貨を記録します。
7同じ関係を再帰とメモ化で計算
必要な金額から小さい金額へ再帰します。cacheは同じ引数の結果を保存し、次の呼び出しで再利用します。
@cache同じ引数の結果を再利用
def best(x):金額xの最小枚数
if x == 0: return 00円は0枚
return min(best(x-c)+1 for c in coins if c <= x)各最終硬貨の候補から最小値基底条件は金額0です。硬貨1があるため、この演習の非負整数金額は全て作れます。メモ化関数はcoinsを参照するので、硬貨の種類を変えた場合は古いキャッシュを消す必要があります。
8再利用された計算
最初の呼び出しと、同じ金額をもう一度呼び出した後のキャッシュ情報を表示します。missesは実際に関数の本体を計算した異なる引数の数です。
best(6), best.cache_info()初回の結果とキャッシュ; best(6), best.cache_info()同じ金額を再利用どちらも2枚です。2回目はhitsが1増え、missesは増えません。表を小さい順に埋める方法と、必要な部分問題をメモ化する方法は、同じ最適値の関係を異なる順序で計算しています。
まとめ
貪欲な選択が全体の最適解になるとは限りません。硬貨1・3・4で金額6が反例です。
動的計画法では最後の選択と残りの最適値を組み合わせ、小さい金額の答えを保存します。
メモ化では同じ部分問題の計算結果を再利用します。入力条件を変える場合はキャッシュの整合性も必要です。
操作履歴と解説を振り返れます。
Python 3
from functools import cache; coins = [1, 3, 4]; amount = 6; greedy = [4, 1, 1]; sum(greedy), len(greedy), [3, 3](6, 3, [3, 3])
dp = [0] + [float('inf')] * amount; dp[0, inf, inf, inf, inf, inf, inf]
dp[1] = dp[0] + 1; dp[2] = dp[1] + 1; dp[0, 1, 2, inf, inf, inf, inf]
candidates = [(c, dp[3-c]+1) for c in coins if c <= 3]; dp[3] = min(n for c, n in candidates); candidates, dp([(1, 3), (3, 1)], [0, 1, 2, 1, inf, inf, inf])
for x in range(4, amount+1):
options = [(c, dp[x-c]+1) for c in coins if c <= x]
dp[x] = min(n for c, n in options)
print(x, options, dp[x])4 [(1, 2), (3, 2), (4, 1)] 1 5 [(1, 2), (3, 3), (4, 2)] 2 6 [(1, 3), (3, 2), (4, 3)] 2
last = next(c for c in coins if c <= 6 and dp[6] == dp[6-c]+1); remaining = 6-last; second = next(c for c in coins if c <= remaining and dp[remaining] == dp[remaining-c]+1); dp, [last, second], last+second([0, 1, 2, 1, 1, 2, 2], [3, 3], 6)
@cache
def best(x):
if x == 0: return 0
return min(best(x-c)+1 for c in coins if c <= x)best(6), best.cache_info(); best(6), best.cache_info()(2, CacheInfo(hits=7, misses=7, maxsize=None, currsize=7)) (2, CacheInfo(hits=8, misses=7, maxsize=None, currsize=7))
演習完了