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に辿り着くまでに支払うコストの総和の最小値を求めてください。

Frog1.py

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に辿り着くまでに支払うコストの総和の最小値を求めてください。

Frog2.py

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日以上連続で同じ活動を行うことはできません。
太郎君が得る幸福度の総和の最大値を求めてください。

vacaton.py

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以下でなければなりません。
太郎君が持ち帰る品物の価値の総和の最大値を求めてください。

knapsack1.py

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 以下でなければなりません。
太郎君が持ち帰る品物の価値の総和の最大値を求めてください。

knapsack2.py

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)