A - Frog 1 There are N scaffolds. The scaffolds are numbered 1,2,…, N. For each i (1 ≤ i ≤ N) the height of the scaffold i is hi. Initially, there is a frog on scaffold 1. The frog repeats the following actions several times, trying to reach scaffolding N. Scaffolding i when in scaffolding i+1 or i+Jump to 2. At this time, if the scaffolding of the jump destination is j, the cost|hi−hj|Pay. Find the minimum total cost that the frog will pay to reach scaffold 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)
The cost is 0 for scaffold 1. The cost is abs (h0-h1) because scaffold 2 can only be routed from scaffold 1. Therefore, there are multiple options for scaffolding 2 and above, but for scaffolding i, the only options are scaffolding i-1 or i-2. min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2])) Is calculated as the cost of scaffolding i.
B - Frog 2 There are N scaffolds. The scaffolds are numbered 1,2,…, N. For each i (1 ≤ i ≤ N), the height of the scaffold i is hi. Initially, there is a frog on scaffold 1. The frog repeats the following actions several times, trying to reach scaffolding N. When in scaffold i, jump to one of scaffold i + 1, i + 2,…, i + K. At this time, if the scaffolding of the jump destination is j, the cost|hi−hj|Pay. Find the minimum total cost that the frog will pay to reach scaffold 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 pattern with more choices for jumping problems. It can be solved just by making a nested structure of for. Finally, [0, 30, 20, 30, 40, 30, 20, 30, 40, 40] Will be.
C - Vacation Taro's summer vacation will start tomorrow. Taro decided to make a plan for the summer vacation. Summer vacation consists of N days. For each i (1 ≤ i ≤ N), on day i, Taro chooses one of the following activities. A: Swim in the sea. Get happiness ai. B: Get rid of insects in the mountains. Get happiness bi. C: Do your homework at home. Get happiness ci. Taro is tired of it, so he can't do the same activity for more than two days in a row. Find the maximum value of the total happiness that Taro gets.
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)
Calculate when A is selected, when B is selected, and when C is selected in each procedure, and the final maximum procedure is calculated backward. [[0, 0, 0], [10, 40, 70], [90, 120, 120], [150, 180, 210]] Will be.
D - Knapsack 1 There are N items. Items are numbered 1,2,…, N. For each i (1 ≤ i ≤ N), the item i weighs wi and has a value of vi. Taro chose some of the N items and decided to put them in a knapsack and take them home. The capacity of the knapsack must be W, and the total weight of the items to be brought back must be W or less. Find the maximum sum of the values of the items that Taro brings back.
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)
A typical problem of the knapsack problem. The number is piled up with for i in range (N), and the weight is expressed with for j in range (W + 1). Both the value and the weight can be considered by adding the value obtained by subtracting the weight of the overlapping items from j.
E - Knapsack 2 There are N items. Items are numbered 1,2,…, N. For each i (1 ≤ i ≤ N), the item i weighs wi and has a value of vi. Taro chose some of the N items and decided to put them in a knapsack and take them home. The capacity of the knapsack must be W, and the total weight of the items to be brought back must be W or less. Find the maximum sum of the values of the items that Taro brings back.
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)
Recommended Posts