Solve with Python [100 selections of past questions that beginners and intermediates should solve] (039 --045 Dynamic programming: Knapsack DP variant)

1. Purpose

Solve 100 past questions that beginners and intermediates should solve in Python. The goal is to turn light blue by the time you finish solving everything.

This article is "039-045 Dynamic Programming: Knapsack DP Variants".

2. Summary

The problem can be solved if you can actually write the target dp table, but it is difficult to solve if you can not imagine the table.

3. Main story

039 --045 Dynamic programming: Knapsack DP variant

039. JOI 2011 Qualifying 4-1st grade

Answer

N = int(input())
num = list(map(int, input().split()))
dp = [[0] * (N-1) for _ in range(21)]

for i in range(21):
    if i == num[0]:
        dp[i][0] = 1

for j in range(1, N-1):
    for i in range(21):
        if dp[i][j-1] <= 0:
            continue
        
        if i - num[j] >= 0:
            dp[i - num[j]][j] += dp[i][j-1]
        if i + num[j] <= 20:
            dp[i + num[j]][j] += dp[i][j-1]

answer = dp[num[-1]][N-2]
print(answer)

The dp table matches the row subscript with the calculated total value, the column subscript with the given integer subscript. In the dp table, record "the number of cases where the calculation result is exactly i by column j".

The dp table created in Input Example 1 is as follows. The answer is dp [8] [9](= 10).

    0  1  2  3  4  5  6  7   8   9
0   0  0  0  0  0  0  1  2   4   8
1   0  0  0  0  1  0  0  0   0   0
2   0  0  0  0  0  1  1  3   6  12
3   0  0  1  1  1  0  0  0   0   0
4   0  0  0  0  0  1  2  4   8   8
5   0  1  0  1  1  0  0  0   0   0
6   0  0  0  0  0  1  3  5  10  12
7   0  0  1  1  0  0  0  0   0   0
8   1  0  0  0  0  2  3  4   8  10
9   0  0  1  1  1  0  0  0   0   0
10  0  0  0  0  0  2  4  6  12  12
11  0  1  0  1  1  0  0  0   0   0
12  0  0  0  0  0  2  2  4   8  10
13  0  0  1  1  1  0  0  0   0   0
14  0  0  0  0  0  0  3  6  12  10
15  0  0  0  0  1  0  0  0   0   0
16  0  0  0  0  0  1  1  3   6   8
17  0  0  0  1  1  0  0  0   0   0
18  0  0  0  0  0  1  2  3   6  12
19  0  0  0  0  1  0  0  0   0   0
20  0  0  0  0  0  1  1  1   2   8

I think it's a good idea to write this table first and then write the code that realizes this table. I imagine that once you get used to it, you'll be able to write code directly without writing this table, but I can't solve it without writing a table yet.

040. JOI 2012 Qualifying 4-Pasta

Answer

N, K = map(int, input().split()) #K days out of N days have already been decided
pastas = [0] * (N+1)
for _ in range(K):
    A, B = map(int, input().split())
    pastas[A] = B
dp = [[0] * (N+1) for _ in range(4)]
MOD = 10**4

dp[1][0] = 1

for j in range(1, N+1):
    if pastas[j] == 0:
        for i in range(1, 4):
            for k in range(1, 4):
                dp[i][j] += dp[k][j-1]
        for i in range(1, 4):
            if j -2 > 0 and dp[i][j-1] > 0 and dp[i][j-2] > 0:
                dp[i][j-1] -= dp[i][j-2] #Subtract the one 2 days ago so that it does not continue for 3 days or more
                dp[i][j] -= dp[i][j-2] #Subtract the one 2 days ago so that it does not continue for 3 days or more
    else:
        for k in range(1, 4):
            dp[pastas[j]][j] += dp[k][j-1]
        if j - 2 > 0 and dp[pastas[j]][j-1] > 0 and dp[pastas[j]][j-2] > 0:
            dp[pastas[j]][j-1] -= dp[pastas[j]][j-2] #Subtract the one 2 days ago so that it does not continue for 3 days or more
            dp[pastas[j]][j] -= dp[pastas[j]][j-2] #Subtract the one 2 days ago so that it does not continue for 3 days or more

answer = 0
for i in range(1, 4):
    answer += dp[i][-1]
print(answer % MOD)

There is a feeling that it was forcibly solved, but it is AC above. In many answer examples, the dp table is created in 3D, but it is difficult to get an image in 3D and it was solved in 2D. The goal of the dp table to be created is to create the following table with the row subscript as the pasta type, the column subscript as the number of days, and the contents of the table as the number of cases ( In case of input example 2)

   0  1  2  3   4   5   6    7    8     9    10    11    12    13    14    15     16     17      18      19       20
0  0  0  0  0   0   0   0    0    0     0     0     0     0     0     0     0      0      0       0       0        0
1  1  1  2  8   0  22  38  104  306  1120     0  1120  3360     0  3360  6720  16800  50400  134400  366240  1370880
2  0  1  2  8   0  22  38  104  410     0  1120  1120     0  3360     0  6720  20160  47040  134400  369600  1370880
3  0  1  2  6  16   0  44  120  404     0     0  1120     0     0  3360  6720  16800  50400  134400  366240  1370880

The process of creating this table is as follows. Since it is long, you can put it up to `` `j = 5```.

j=1----------
When added normally ↓
   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
0  0  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
1  1  1  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2  0  1  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
3  0  1  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
After erasing consecutive things ↓
   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
0  0  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
1  1  1  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2  0  1  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
3  0  1  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
j=2----------
When added normally ↓
   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
0  0  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
1  1  1  3  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2  0  1  3  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
3  0  1  3  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
After erasing consecutive things ↓
   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
0  0  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
1  1  1  3  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2  0  1  3  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
3  0  1  3  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
j=3----------
When added normally ↓
   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
0  0  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
1  1  1  3  9  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2  0  1  3  9  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
3  0  1  3  9  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
After erasing consecutive things ↓
   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
0  0  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
1  1  1  2  8  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2  0  1  2  8  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
3  0  1  2  8  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
j=4----------
When added normally ↓
   0  1  2  3   4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
0  0  0  0  0   0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
1  1  1  2  8   0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2  0  1  2  8   0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
3  0  1  2  8  24  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
After erasing consecutive things ↓
   0  1  2  3   4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
0  0  0  0  0   0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
1  1  1  2  8   0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2  0  1  2  8   0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
3  0  1  2  6  22  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
j=5----------
When added normally ↓
   0  1  2  3   4   5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
0  0  0  0  0   0   0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
1  1  1  2  8   0  22  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2  0  1  2  8   0  22  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
3  0  1  2  6  22  22  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
After erasing consecutive things ↓
   0  1  2  3   4   5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
0  0  0  0  0   0   0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
1  1  1  2  8   0  22  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2  0  1  2  8   0  22  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
3  0  1  2  6  16  16  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0

dpIf you can create a table, the sum in the last column will be the answer.

041. JOI 2013 Qualifying 4-Hot Days

Answer

D, N = map(int, input().split()) #D day, N kinds of clothes
T = [0] + [int(input()) for _ in range(D)] #Each day's temperature
clothes = [tuple(map(int, input().split())) for _ in range(N)] #(Lower limit temperature, upper limit temperature, flashiness)
dp = [[0] * (D+1) for _ in range(N)]

for j in range(2, D+1):
    for i in range(N):
        if T[j] < clothes[i][0] or clothes[i][1] < T[j]:
            continue
        score = 0
        for k in range(N):
            if T[j-1] < clothes[k][0] or clothes[k][1] < T[j-1]:
                continue
            score = max(score,
                        abs(clothes[i][2] - clothes[k][2]) + dp[k][j-1])
        dp[i][j] = score

answer = 0
for i in range(N):
    answer = max(answer, dp[i][-1])

print(answer)

The goal of this `` `dp``` table is to create the following table with the row subscript as clothes, the column subscript as the date, and the content as the absolute value of flashiness. (In the case of input example 1)

   0  1   2   3
0  0  0   0   0
1  0  0  50   0
2  0  0  20  80
3  0  0   0   0

If you can create this table, the answer is the maximum value in the last column.

042. JOI 2015 Qualifying 4-Silk Road

Answer

INF = float('inf')
N, M = map(int, input().split()) # N+1 city, need to carry within M days
D = [0] + [int(input()) for _ in range(N)] #City distance
C = [0] + [int(input()) for _ in range(M)] #Bad weather. Fatigue is C*D but 0 if not moving
MAX_break = M - N

# dp[i][j] :=Minimum fatigue to reach i by day j

dp = [[INF] * (M+1) for _ in range(N+1)]

for j in range(M+1):
    dp[0][j] = 0

for i in range(1, N+1):
    for j in range(1, M+1):
        dp[i][j] = min(dp[i][j-1],
                       dp[i-1][j-1] + D[i] * C[j])

print(dp[-1][-1])

The goal of this `` `dp``` table is to create a table like the one below, with the row subscripts moved, the column subscripts as dates, and the contents as the minimum distance. (In the case of input example 1)

     0      1       2       3       4       5
0  0.0    0.0     0.0     0.0     0.0     0.0
1  inf  500.0   300.0   150.0   150.0   150.0
2  inf    inf  1250.0   675.0   675.0   675.0
3  inf    inf     inf  1475.0  1275.0  1125.0

If this table can be created, the answer is `dp [-1] [-1] `.

043. Pakencamp 2019 D --Pakencamp Flag

Answer

import numpy as np

INF = float('inf')
N = int(input())
S = [[''] + list(input()) for _ in range(5)]
S_count = np.zeros((4, N+1))
for j in range(1, N+1):
    for i in range(5):
        if S[i][j] == 'R':
            S_count[0, j] += 1
        if S[i][j] == 'B':
            S_count[1, j] += 1
        if S[i][j] == 'W':
            S_count[2, j] += 1
        if S[i][j] == '#':
            S_count[3, j] += 1

S_to_use = np.zeros((3, N+1))
for j in range(1, N+1):
    for i in range(3):
        S_to_use[i, j] = S_count[:, j].sum() - S_count[i, j]

dp = np.full((3, N+1), INF)
dp[:, 0] = 0
# dp[i, j] :=Minimum value when painting the jth column on i

for j in range(1, N+1):
    for i in range(3):
        for k in range(3):
            if i == k:
                continue
            dp[i, j] = min(dp[i, j],
                           dp[k, j-1] + S_to_use[i, j])

answer = dp[:, -1].min()
print(int(answer))

In this `` `dp``` table, the subscript of the row is the color of the flag (R: 0, B: 1, W: 2), the subscript of the column is the column number, and the content is the smallest filled cell. As a number, the goal is to create a table like the one below. (In the case of input example 4)

     0    1    2     3     4     5     6     7
0  0.0  4.0  6.0  12.0  13.0  15.0  18.0  23.0
1  0.0  3.0  8.0  11.0  11.0  17.0  19.0  21.0
2  0.0  4.0  7.0   8.0  15.0  15.0  20.0  21.0

The answer is the minimum value in the rightmost column of this table.

In this issue, we had to devise a pre-processing before creating the dp table. Specifically, `S_to_use` in the answer code, which means, for example, S_to_use [0, 2] `` `, which is necessary to paint the second column of the flag on R. Represents the number of squares. If I could create this, I thought it wouldn't be that difficult to create a dp table.

044. AOJ 1167 --Pollock Forecast

Answer (TLE)

def cal(i):
    return i * (i + 1) * (i + 2) // 6

def main(n):
    proku = [0]
    proku_odd = [0]
    for i in range(1, 201):
        num = cal(i)
        proku.append(num)
        if num % 2 != 0:
            proku_odd.append(num)

    dp = [0] * (n+1)
    dp_odd = [0] * (n+1)

    for j in range(n+1):
        dp[j] = j
        dp_odd[j] = j

    for i in range(1, len(proku)):
        for j in range(1, n+1):
            if j-proku[i] < 0:
                continue
            if dp[j] > dp[j-proku[i]] + 1:
                dp[j] = dp[j-proku[i]] + 1

    for i in range(1, len(proku_odd)):
        for j in range(1, n+1):
            if j-proku_odd[i] < 0:
                continue
            if dp_odd[j] > dp_odd[j-proku_odd[i]] + 1:
                dp_odd[j] = dp_odd[j-proku_odd[i]] + 1

    print(dp[-1], dp_odd[-1])


if __name__ == "__main__":
    while True:
        n = int(input())
        if n == 0:
            break
            
        main(n)

tleI haven't fixed it, but I think it's probably this. It's a little hard to understand the problem statement, but it's not that hard to do, it's just a normal `` dp```.

It can be solved in the same way as the knapsack problem (problem 36) that allows duplicates.

045. AOJ 2199 --Differential pulse code modulation

Answer (TLE)

def main(N, M, C, X):
    dp = [[INF] * 256 for _ in range(N+1)]
    dp[0][128] = 0

    for i in range(1, N+1):
        for j in range(256):

            for k in range(M):
                next_j = j + C[k]
                next_j = max(0, min(255, next_j))

                dp[i][next_j] = min(dp[i][next_j],
                                    dp[i-1][j] + pow(next_j - X[i-1], 2))

    answer = min(dp[N][:])
    
    return answer


if __name__ == "__main__":
    INF = float('inf')
    answer_list = []
    while True:
        
        N, M = map(int, input().split()) #N is the number of inputs, M is the number of numbers in the codebook
        if N == M == 0:
            break

        C = [int(input()) for _ in range(M)] #Codebook
        X = [int(input()) for _ in range(N)] #Input value

        answer_list.append(main(N, M, C, X))

    for answer in answer_list:
        print(answer)

The problem is difficult to read. Again, the above code would be `` `TLE```. I think this is correct because all the answers are the same locally. It was a little difficult to speed up, so I will do it when I feel like it.