動的計画法２ コイン問題
動的計画法シリーズ，２個目の例題です．この問題も結構有名な問題らしく，ググるといろいろ出てきます．今回は再帰を使ってこの問題を解く方法を考えて，そこから動的計画法の表を作ってみたいと思います．
問題定義
額面が C1, C2, ... , Cm のコインを使って，n 円を支払うときの最小のコインの枚数をもとめよ． ただし，各額面のコインは何回使ってもよいものとする．
問題のイメージは下記のとおりです．
１．問題の解き方（統治分割法＆貪欲法）
まずはいつものごとく，貪欲に解いてみます．ナップザック問題とこの問題が違うところは，同一のコインを何枚使ってもいいというところです．この違いは再帰関数内の分岐条件の違いとして現れます．一つの額面を一回しか使えないという制限がついている場合，分岐は次のようになります．
関数を次のように定義します．
get_coin_num(cur_idx, amt, coin_list) cur_idx : 0 ~ cur_idx-1 が支払いに使用できるコインの種類 amt : 支払い金額 coin_list : コインの額面リスト
つまり，get_coin_num(3, 10, coin_list) は，coin_list の 0 ~ 2 までのコインを使って amt の金額を支払う際のコインの最小枚数です．
自分を使った場合の枚数：get_coin_num(cur_idx-1, amt-coin_list[cur_idx], coin_list) + 1 自分を使わなかった場合の枚数：get_coin_num(cur_idx-1, amt, coin_list)
このコインを使おうが，使うまいが，同一 idx のコインを考慮するのは一回だけなので，再帰関数を呼び出すときには cur_idx + 1 としてそれ以降の再帰関数ではこの額面のコインが扱われることはありません．一方で，同一のコインを何回も使っていい場合，分岐を次のように書き替える必要があります．
自分を使った場合の枚数：get_coin_num(cur_idx, amt-coin_list[cur_idx], coin_list) + 1 自分を使わなかった場合の枚数：get_coin_num(cur_idx-1, amt, coin_list)
これをコードに落とすと，下記のようになります．
def get_num_coin_rec(amt, coin_list):
return get_num_coin_rec_int(len(coin_list)-1, amt, coin_list)
def get_num_coin_rec_int(cur_idx, amt, coin_list):
if (amt == 0):
return 0
elif (amt < 0 or cur_idx == -1):
return sys.maxsize
val1 = get_num_coin_rec_int(cur_idx, amt-coin_list[cur_idx], coin_list) + 1
val2 = get_num_coin_rec_int(cur_idx-1, amt, coin_list)
return min(val1, val2)
if __name__ == '__main__':
print("Coin Changing Problem")
amt = 15
coin_list = [1, 2, 7, 8, 12, 50]
print(get_num_coin_rec(amt, coin_list))
２．問題の解き方（統治分割法＆メモ化再帰）
関数を見てわかる通り，コールされるたびに変わる変数は cur_idx と amt です．よって，この 2 変数を添え字としたメモを作成すれば，上記関数をメモ化再帰に買えることができます．
def get_num_coin_rec_memo(amt, coin_list):
memo = np.zeros((len(coin_list)+1, amt+1))
memo.fill(sys.maxsize)
return get_num_coin_rec_memo_int(len(coin_list)-1, amt, coin_list, memo)
def get_num_coin_rec_memo_int(cur_idx, amt, coin_list, memo):
if (amt == 0):
val = 0
elif (cur_idx == -1 or amt < 0):
val = sys.maxsize
elif (memo[cur_idx, amt]!=sys.maxsize):
val = memo[cur_idx, amt]
else:
val1 = get_num_coin_rec_memo_int(cur_idx, amt-coin_list[cur_idx], coin_list, memo) + 1
val2 = get_num_coin_rec_memo_int(cur_idx-1, amt, coin_list, memo)
memo[cur_idx, amt] = min(val1, val2)
val = memo[cur_idx, amt]
return val
if __name__ == '__main__':
print("Coin Changing Problem")
amt = 15
coin_list = [1, 2, 7, 8, 12, 50]
print(get_num_coin_rec_memo(amt, coin_list))
３．問題の解き方（動的計画法）
１と２のコードの分岐のさせ方から，下記のように漸化式が求まります．
table[0][j] = INFINITY (０円の額面のコインを使うと，無限枚必要．) table[i][j] = table[i-1][j] (if j < amt[i]) table[i][j] = min(table[i][j-amt[i]]+1, table[i-1][j]) (if j < amt[i])
漸化式が求まっていったので，結局は i, j が小さいところから表を埋めていけば，DPでこの問題を解けます．実装は，下記のようになります．
def get_num_coin_dp(amt, coin_list):
cnt_tbl = np.zeros((len(coin_list)+1, amt+1), dtype=int)
cnt_tbl.fill(255)
cnt_tbl[:, 0] = 0
for i in range(1, len(coin_list)+1):
for j in range(1, amt+1):
if (j < coin_list[i-1]):
cnt_tbl[i, j] = cnt_tbl[i-1, j]
else:
cnt_tbl[i, j] = min(cnt_tbl[i-1, j], cnt_tbl[i, j-coin_list[i-1]] + 1)
return cnt_tbl[len(coin_list), amt]
if __name__ == '__main__':
print("Coin Changing Problem")
amt = 15
coin_list = [1, 2, 7, 8, 12, 50]
print(get_num_coin_dp(amt, coin_list))上記の計算でも止まるテーブルを可視化すると，下記のようになります．
[[ 0 INF INF INF INF INF INF INF INF INF INF INF INF INF INF INF] [ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15] [ 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8] [ 0 1 1 2 2 3 3 1 2 2 3 3 4 4 2 3] [ 0 1 1 2 2 3 3 1 1 2 2 3 3 4 2 2] [ 0 1 1 2 2 3 3 1 1 2 2 3 1 2 2 2] [ 0 1 1 2 2 3 3 1 1 2 2 3 1 2 2 2]]
だいぶ動的計画法の考え方に慣れてきましたが，問題を解くコツは
１．再帰的に求める方法を考える．
２．再帰関数の分岐から漸化式を作る．
３．漸化式を使って，ボトムアップで表を埋めていく
という感じですかね．
