Supershipの名畑です。手塚治虫 ブラック・ジャック展は本当に熱い展示でした。多くの方が短くとも3時間程度は滞在していたのではないでしょうか。
はじめに
前に「AtCoder アルゴリズムと数学 009 - Brute Force 2 解答例(Pythonでのbit全探索 / 動的計画法のシンプルなコード例)」という記事で動的計画法について書きました。
AtCoderをやる上では避けては通れない動的計画法ですが、私、本当に苦手なんです。すぐにその内容が頭から飛んでしまう。きちんと理解できていないってことなと思います。
未来の自分自身のため、AtCoderにおける動的計画法の基本的な問題を5問選んで Python(PyPy 3.10-v7.3.12) での解答例をここに残しておきます。見直し用です。
私と同じような方の役にも立つと嬉しいです。
かなり初歩的なため、すでにきっちり理解できている方にとっては物足りない内容かとは思います。
動的計画法とは
そもそも動的計画法とはなんなのか。
Wikipediaによると下記の説明でした。
動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。
と、文章で説明されてもぴんと来ない方のための5問になります。
1 - 部分和問題
問題：アルゴリズムと数学 演習問題集 009 - Brute Force 2
先述の記事で取り上げた問題です。
正の整数が書かれたN枚のカードにおいて合計がSになる組み合わせがあるかをYes or Noで答えるという問題です。
たとえばNが3で、各カードをA0、A1、A2とします。
そして書かれた整数がA0は1、A1は2、A2は3だとします。
A0しかカードがない場合、とりうる合計値は0と1のみです。A0を選ぶか選ばないかの2択しかないので。
A1もある場合、とりうる合計値は下記の通りで0、1、2、3です。0と1に対してさらにA1を選ぶか選ばないかの2択が発生するため。
- 0 + 0 = 0
- 0 + 2 = 2
- 1 + 0 = 1
- 1 + 2 = 3
A2もある場合、とりうる合計値は下記です。
- 0 + 0 = 0
- 0 + 3 = 3
- 1 + 0 = 1
- 1 + 3 = 4
- 2 + 0 = 2
- 2 + 3 = 5
- 3 + 0 = 3
- 3 + 3 = 6
0、1、2、3、4、5、6です。
つまり、Sがこの7つの中にあればYesとなります。
コードにすると下記です。
N, S = map(int, input().split())
A = list(map(int, input().split()))
dp = [False] * (S + 1) # 0〜Sまでの値をとりうるかを格納する配列
dp[0] = True # 0のみTrueにしておく
for i in range(N): # 0枚目から順番にカードを見ていく
for j in reversed(range(0, S)): # dpの値がループ途中で変わらないようにreversedしている
if dp[j] and j + A[i] <= S:
dp[j + A[i]] = True
if dp[S]: # Sをとりうるか判定する
print('Yes')
else:
print('No')
2 - 部分和問題 - 最小値
問題：アルゴリズムと数学 演習問題集 028 - Frog 1
N個の足場があり、それぞれの高さはhという配列に格納されています。
カエルは一つ先の足場か二つ先の足場にのみ移動でき、その際のコストは今いる足場との高さの差です。
カエルがN個目の足場にたどり着くまでのコストの総和の最小値を求めるという問題です。
先述の問題では値をとりうるか否かのみが求められましたが、この問題では最小値を求めます。
考え方は同じです。1個目の足場にたどり着くまでのコストの最小値、2個目の足場にたどり着くまでのコストの最小値……N個目の足場にたどり着くまでのコストの最小値を順番に求めていきます。
下記はコードです。コードを簡潔にしたかったため足場を0〜N-1としてあるのでご注意ください。
N = int(input())
h = list(map(int, input().split()))
# i個目の足場にたどり着くまでのコストの最小値を格納する配列
dp = [float('inf')] * N # 初期値として無限大を入れておきます
dp[0] = 0 # 最初にいる足場までのコストを0とする
for i in range(0, N - 1): # 最初の足場から最後の1個前の足場まで
for dist in [1, 2]: # 1つ先の足場に移動した時と2つ先の足場に移動した時のコストの最小値を記録する
if i + dist < N: # 移動可能である
diff = abs(h[i + dist] - h[i]) # 高さの差
if dp[i] + diff < dp[i + dist]: # 最小値である
dp[i + dist] = dp[i] + diff
print(dp[N - 1]) # 最後の足場にいるときの最小値を出力する
3 - 部分和問題 - 合計値の最小化
N品の料理をオーブンで作ろうとしており、それぞれのオーブン利用時間はTという配列に格納されています。
オーブンは2つだけです。
すべての料理を作り終わるのにかかる時間は何秒かという問題です。
仮にオーブンが1台であれば、Tの総和が解答となります。
今回はオーブンが2台のため、解答はTの総和/2以上となります。片方のオーブンの使用時間を短くすればするほどにもう片方のオーブンの使用時間は長くなりますので。
また、片方のオーブンでの料理時間をAとするならば、もう片方のオーブンを使う時間はTの総和 - Aとなるため、片方のオーブンでの料理時間だけを求めれば自ずと全料理の完成時間が求められます。「A」と「Tの総和 - A」の大きい方が全料理の完成時間です。
つまりは、全組み合わせのうちでTの総和/2以上での最小値を求めればよいとなります。
たとえば料理が2つのときを考えます。
それぞれが10秒と20秒であるならば、1番目の料理までの組み合わせは0秒(Aを作らない)と10秒(Aを作る)の2つのみです。
2番目の料理までの組み合わせとなると、0秒と10秒に対して20秒を足すか足さないかの組み合わせなので合計4パターンで0秒、10秒、20秒、30秒となります。
合計料理時間は30秒ですので15秒以上での最小値が解答となります。つまり20秒です。
これをコードにしてみます。
今回は dp[N][Tの総和 + 1] という配列を用意します。
1次元目はi番目(0〜)までの料理の組み合わせにおいてを意味し、2次元目は合計料理時間をこの秒数にできるかを意味します。
import math
N = int(input())
T = list(map(int, input().split()))
total = sum(T) # Tの合計値
# 配列を用意する
dp = [[False] * (total + 1) for i in range(N)]
dp[0][0] = True # 0番目の料理を作らない時
dp[0][T[0]] = True # 0番目の料理を作った時
# 1番目の料理から最後の料理までをループする
for i in range(1, N):
for j in range(total):
if dp[i - 1][j]: # i-1番目の料理まででとりうる料理時間に対して
dp[i][j] = True # i番目の料理を作らない時
dp[i][j + T[i]] = True # i番目の料理を作る時
# total/2以上の最小値を求める
for i in range(math.ceil(total / 2), total + 1):
if dp[N - 1][i]:
print(i)
exit()
4 - 最適化問題
問題：Educational DP Contest / DP まとめコンテスト D - Knapsack 1
重さwと価値vが割り当てられたN個の品物があります。
許容重量がWのナップサックに価値が最大化するように品物を入れてくださいという問題です。
いわゆるナップサック問題というやつですね。
これも二次元の配列を用意して解くことができます。
dp[N+1][W+1] の配列を用意します。
たとえば dp[3][2] ならば3番目の品物までで許容重量が2までの価値の最大値を示します。
コードにすると下記です。
N, W = map(int, input().split())
v = [0] * N
w = [0] * N
for i in range(N):
w[i], v[i] = map(int, input().split())
# 2次元配列を初期値0で用意する
dp = [[0 for i in range(W + 1)] for j in range(N + 1)]
for i in range(N): # N個の荷物を順番に見る
for j in range(W + 1): # ナップサックの許容重量を0〜Wと仮定する
if w[i] <= j: # i番目の品物がナップサックの許容重量以下である
# ナップサックに入れた方が価値が上がるかどうかを求める
dp[i + 1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j])
else: # ナップサックに入れられないのでi-1番目の品物までの時の価値をそのまま用いる
dp[i + 1][j] = dp[i][j]
print(dp[N][W])
5 - 2次元最適化問題
問題：第11回アルゴリズム実技検定 H - 2つのナップサック
ナップサックが2つになったケースです。
dpを3次元配列としてます。
2つのナップサックの許容重量をAとBとすると dp[N+1][A+1][B+1] です。
コードは以下です。
N, A, B = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(0, N):
w[i], v[i] = map(int, input().split())
# 3次元配列を初期値0で用意する
dp = [[[0 for k in range(B + 1)] for j in range(A + 1)] for i in range(N + 1)]
for i in range(N):
for w1 in range(A + 1): # 1つ目のナップサックの許容重量
for w2 in range(B + 1): # 2つ目のナップサックの許容重量
# i番目のお菓子をいずれかのナップサックに入れられるか判定する
if w[i] <= w1 or w[i] <= w2:
# 1つ目のナップサックに入れられる
if w[i] <= w1:
dp[i + 1][w1][w2] = max(dp[i][w1 - w[i]][w2] + v[i], dp[i][w1][w2])
# 2つ目のナップサックに入れられる
# 1つ目のナップサックに入れられたケースを考慮してdp[i + 1][w1][w2]もmaxの引数に追加する
if w[i] <= w2:
dp[i + 1][w1][w2] = max(dp[i][w1][w2 - w[i]] + v[i], dp[i][w1][w2], dp[i + 1][w1][w2])
# ナップサックに入れられないのでi-1番目格納時点の美味しさのままとする
else:
dp[i + 1][w1][w2] = dp[i][w1][w2]
print(dp[N][A][B])
最後に
こういうのがさくっと頭から出てくるようになりたい。
宣伝
SupershipのQiita Organizationを合わせてご覧いただけますと嬉しいです。他のメンバーの記事も多数あります。
Supershipではプロダクト開発やサービス開発に関わる方を絶賛募集しております。
興味がある方はSupership株式会社 採用サイトよりご確認ください。