Educational DP Contest / DP まとめコンテストを通じて動的計画法を学ぶ(A~E)
A - Frog 1
N 個の足場があります。 足場には 1,2,…,Nと番号が振られています。 各 i (1≤i≤N) について足場iの高さはhiです。
最初、足場1にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 Nまで辿り着こうとしています。
足場 iにいるとき、足場 i+1または i+2へジャンプする。 このとき、ジャンプ先の足場を jとすると、コスト |hi−hj|を支払う。
カエルが足場Nに辿り着くまでに支払うコストの総和の最小値を求めてください。
N = 6
h = [30 10 60 10 60 50]
def frog1(N, h):
dp = [float('inf')]*(N)
dp[0]=0
dp[1]=abs(h[0]-h[1])
if N>=2:
for i in range(2,N):
dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))
print(dp[-1])
frog1(N,h)
足場1ではコストは0。足場2では足場1からしか経由できないため,コストはabs(h0-h1)。
よって足場2以上から複数選択肢が出てくるが、足場iに対して選択肢は足場i-1 or i-2しかないため
min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))
を計算して足場iのコストとする。
B - Frog 2
N個の足場があります。 足場には 1,2,…,Nと番号が振られています。
各 i(1≤i≤N) について、足場 iの高さは hiです。
最初、足場 1にカエルがいます。 カエルは次の行動を何回か繰り返し、足場Nまで辿り着こうとしています。
足場 iにいるとき、足場 i+1,i+2,…,i+Kのどれかへジャンプする。
このとき、ジャンプ先の足場を jとすると、コスト |hi−hj|を支払う。
カエルが足場Nに辿り着くまでに支払うコストの総和の最小値を求めてください。
N,K = 10,4
h = [40, 10, 20, 70, 80, 10, 20, 70, 80, 60]
def frog2(N,k,h):
dp = [float("inf")]*N
dp[0]=0
for i in range(1,N):
for j in range(1,K+1):
if i-j >= 0:
dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]))
else:
break
print(dp[-1])
frog2(N,K,h)
A問題のジャンプの選択肢が増えたパターン。
forの入れ子構造にするだけで解ける。最終的に、
[0, 30, 20, 30, 40, 30, 20, 30, 40, 40]
となる。
C - Vacation
明日から太郎君の夏休みが始まります。 太郎君は夏休みの計画を立てることにしました。
夏休みはN日からなります。
各 i (1≤i≤N) について、i日目には太郎君は次の活動のうちひとつを選んで行います。
A: 海で泳ぐ。幸福度aiを得る。
B: 山で虫取りをする。幸福度 biを得る。
C: 家で宿題をする。幸福度ciを得る。
太郎君は飽き性なので、2日以上連続で同じ活動を行うことはできません。
太郎君が得る幸福度の総和の最大値を求めてください。
N = 3
c = [[10,40,70],[20,50,80],[30,60,90]]
def vacation(N,c):
dp = [[0]*(3) for _ in range(N+1)]
for i in range(N):
for j in range(3):
for k in range(3):
if i==0 or j!=k:
dp[i+1][j] = max(dp[i+1][j], dp[i][k]+c[i][j])
print(max(dp[-1]))
vacation(N,c)
各手順でAを選んだ場合、Bを選んだ場合、Cを選んだ場合でそれぞれ計算し、最終的に最大となる手順を逆算的に求める。
[[0, 0, 0], [10, 40, 70], [90, 120, 120], [150, 180, 210]]
となる。
D - Knapsack 1
N個の品物があります。
品物には 1,2,…,Nと番号が振られています。
各 i (1≤i≤N) について、品物 i の重さは wiで、価値は vi です。
太郎君はN個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。
ナップサックの容量はWであり、持ち帰る品物の重さの総和はW以下でなければなりません。
太郎君が持ち帰る品物の価値の総和の最大値を求めてください。
N,W = 3,8
c = [[3, 30],[4,50],[5,60]]
def knapsack1(N,W,c):
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
for j in range(W+1):
if c[i][0] <= j:
dp[i+1][j] = max(dp[i][j],dp[i][j-c[i][0]]+c[i][1])
else:
dp[i+1][j] = dp[i][j]
print(dp[-1][-1])
knapsack1(N,W,c)
ナップザック問題の典型的な問題。
for i in range(N)で個数を重ねていき、for j in range(W+1)で重さを表現。重ねる品物の重さをjから引いた価値の足し算を行うことで価値、重さ双方の考慮ができている。
E - Knapsack 2
N個の品物があります。
品物には 1,2,…,N と番号が振られています。
各i(1≤i≤N) について、品物 i の重さは wi で、価値は vi です。
太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 ナップサックの容量は W であり、持ち帰る品物の重さの総和は W 以下でなければなりません。
太郎君が持ち帰る品物の価値の総和の最大値を求めてください。
N,W = 3,8
c = [[3, 30],[4,50],[5,60]]
def knapsack1(N,W,c):
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
for j in range(W+1):
if c[i][0] <= j:
dp[i+1][j] = max(dp[i][j],dp[i][j-c[i][0]]+c[i][1])
else:
dp[i+1][j] = dp[i][j]
print(dp[-1][-1])
knapsack1(N,W,c)