Résolvez avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (039 --045 Méthode de planification dynamique: variante Knapsack DP)

1. Objet

Résolvez 100 questions passées que les débutants et les intermédiaires devraient résoudre en Python. L'objectif est de devenir bleu clair lorsque vous avez terminé de tout résoudre.

Cet article s'intitule «039-045 Dynamic Planning: Knapsack DP Variant».

2. Résumé

Le problème peut être résolu si vous pouvez réellement écrire la table cible `` dp '', mais il est difficile à résoudre si vous ne pouvez pas imaginer la table.

3. Histoire principale

039 --045 Planification dynamique: variante à dos DP

039. JOI 2011 Qualifying 4-1st Grade

Répondre

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)

La table dp fait correspondre les indices de ligne avec la somme des résultats calculés, les indices de colonne avec les indices entiers donnés. Dans le tableau dp, enregistrez "le nombre de cas où le résultat du calcul est exactement i par la colonne j".

La table dp créée dans l'exemple d'entrée 1 est la suivante. La réponse est 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

Je pense que c'est une bonne idée d'écrire d'abord ce tableau, puis d'écrire le code qui réalise ce tableau. Peut-être qu'en m'y habituant, j'imagine que je pourrai écrire du code directement sans écrire ce tableau, mais je ne peux pas le résoudre sans écrire encore un tableau.

040. JOI 2012 Qualifying 4-Pasta

Répondre

N, K = map(int, input().split()) #K jours sur N jours ont déjà été décidés
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] #Soustrayez celui d'il y a 2 jours pour qu'il ne continue pas pendant 3 jours ou plus
                dp[i][j] -= dp[i][j-2] #Soustrayez celui d'il y a 2 jours pour qu'il ne continue pas pendant 3 jours ou plus
    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] #Soustrayez celui d'il y a 2 jours pour qu'il ne continue pas pendant 3 jours ou plus
            dp[pastas[j]][j] -= dp[pastas[j]][j-2] #Soustrayez celui d'il y a 2 jours pour qu'il ne continue pas pendant 3 jours ou plus

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

Il y a un sentiment qu'il a été résolu de force, mais c'est AC ci-dessus. Dans de nombreux exemples de réponses, la table dp '' est créée en 3D, mais il était difficile d'obtenir une image en 3D et elle a été résolue en 2D. Le but du tableau dp '' à créer est de créer le tableau suivant avec l'indice de ligne comme type de pâtes, l'indice de colonne comme le nombre de jours et le contenu du tableau comme le nombre de caisses ( Dans le cas de l'exemple d'entrée 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

Le processus de création de cette table est le suivant. Comme il est long, vous pouvez le mettre jusqu'à j = 5 ''

j=1----------
Lorsqu'il est ajouté normalement ↓
   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
Après avoir effacé des choses consécutives ↓
   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----------
Lorsqu'il est ajouté normalement ↓
   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
Après avoir effacé des choses consécutives ↓
   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----------
Lorsqu'il est ajouté normalement ↓
   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
Après avoir effacé des choses consécutives ↓
   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----------
Lorsqu'il est ajouté normalement ↓
   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
Après avoir effacé des choses consécutives ↓
   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----------
Lorsqu'il est ajouté normalement ↓
   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
Après avoir effacé des choses consécutives ↓
   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

dpSi vous pouvez créer un tableau, la somme de la dernière colonne est la réponse.

041. JOI 2013 Qualifying 4-Hot Days

Répondre

D, N = map(int, input().split()) #Jour J, N types de vêtements
T = [0] + [int(input()) for _ in range(D)] #Température de chaque jour
clothes = [tuple(map(int, input().split())) for _ in range(N)] #(Température limite inférieure, température limite supérieure, clignotement)
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)

Le but de cette table `` dp '' est de créer une table comme celle ci-dessous, avec l'indice de ligne comme vêtements, l'indice de colonne comme date et le contenu comme valeur absolue de la brillance. (Dans le cas de l'exemple d'entrée 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

Si vous pouvez créer ce tableau, la réponse est la valeur maximale dans la dernière colonne.

042. JOI 2015 Qualifying 4-Silk Road

Répondre

INF = float('inf')
N, M = map(int, input().split()) # N+1 ville, besoin de transporter dans les M jours
D = [0] + [int(input()) for _ in range(N)] #Distance de la ville
C = [0] + [int(input()) for _ in range(M)] #Mauvais temps. La fatigue est C*D mais 0 s'il ne bouge pas
MAX_break = M - N

# dp[i][j] :=Fatigue minimale pour atteindre i le jour 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])

Le but de ce tableau `` dp '' est de créer le tableau suivant avec les indices de ligne déplacés, les indices de colonne comme date et le contenu comme distance minimale. (Dans le cas de l'exemple d'entrée 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

Si cette table peut être créée, la réponse est dp [-1] [-1] '' ''.

043. Pakencamp 2019 D - Drapeau de l'armée de Pakencamp

Répondre

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] :=Valeur minimale lors de la peinture de la jème colonne sur 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))

Dans ce tableau `` dp '', l'indice de ligne est la couleur du drapeau (R: 0, B: 1, W: 2), l'indice de colonne est le numéro de colonne et le contenu est la plus petite des cellules peintes. En tant que nombre, le but est de créer un tableau comme celui ci-dessous. (Dans le cas de l'exemple d'entrée 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

La réponse est la valeur minimale dans la colonne la plus à droite de ce tableau.

Dans ce numéro, nous avons dû concevoir un prétraitement avant de créer la table dp ''. Plus précisément, S_to_use` '' dans le code de réponse, ce qui signifie, par exemple, S_to_use [0, 2] , ce qui est nécessaire pour peindre la deuxième colonne du drapeau sur R. Représente le nombre de carrés. Si je pouvais créer cela, je pensais que ce ne serait pas si difficile de créer une table dp ''.

044. AOJ 1167 --Pollock Forecast

Réponse (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)

tleJe ne l'ai pas corrigé, mais je pense que c'est probablement ça. C'est un peu difficile de comprendre l'énoncé du problème, mais ce n'est pas si difficile à faire, c'est juste un `` dp '' normal.

Il peut être résolu de la même manière que le problème du sac à dos (problème 36) qui autorise les doublons.

045. AOJ 2199 - Modulation du code d'impulsion de différence

Réponse (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 est le nombre d'entrées, M est le nombre de nombres dans le livre de codes
        if N == M == 0:
            break

        C = [int(input()) for _ in range(M)] #Livre de codes
        X = [int(input()) for _ in range(N)] #Valeur d'entrée

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

    for answer in answer_list:
        print(answer)

Le problème est difficile à lire. Encore une fois, le code ci-dessus serait `` TLE ''. Je pense que c'est correct car toutes les réponses sont les mêmes localement. C'était un peu difficile d'accélérer, donc je le ferai quand j'en aurai envie.