Résoudre avec Python [100 questions que les débutants et les intermédiaires devraient résoudre] (034-038 Méthode de planification dynamique: Knapsack DP basic)

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 «034-038 Dynamic Planning: Knapsack DP».

2. Résumé

dpJ'ai eu beaucoup de problèmes.bfs、dfsJ'ai eu beaucoup de problèmes, mais plus que çadpJ'étais inquiet jusqu'à ce que je comprenne un peu. Ce que j'ai fait est le même que pour BFS et `` DFS, et tout en lisant l'explication, déboguez chaque ligne jusqu'à ce que vous puissiez comprendre l'exemple de réponse de AC. Je te suis juste. De plus, comme je ne pouvais pas faire `` DP sur 100 questions soigneusement sélectionnées au début, j'ai d'abord essayé Concours DP typique ```A ~ L Après avoir résolu jusqu'à `` (ou plutôt, j'ai compris en regardant l'exemple de réponse), j'ai commencé. Ensuite, j'ai pu le résoudre un peu.

3. Histoire principale

034 --038 Méthode de planification dynamique: Knapsack DP basic

034. ALDS_10_A --Nombre de Fibonacci

Répondre

n = int(input())
dp = [0] * (n + 1)

dp[0] = 1
dp[1] = 1

for i in range(2, n+1):
    dp[i] = dp[i - 1] + dp[i -2]

print(dp[n])

Si vous l'écrivez récursivement comme ci-dessousTLEParce que ça ne passe pas``DP```C'est un problème avec lequel vous pouvez voir que vous devez le résoudre.

# C'est TLE
num = int(input())

def fib(num):
    if num == 0:
        return 1
    if num == 1:
        return 1

    return fib(num - 1) + fib(num - 2)

print(fib(num))

035. DPL_1_B - 0,1 problème de sac à dos

####Répondre

 N, W = map (int, input (). Split ()) # N items, W est la capacité de poids
 p = [(0, 0)] + [tuple (map (int, input (). split ())) for _ in range (N)] # Goods-> (Value, Weight)
 dp = [[0] * (W + 1) for _ in range (N + 1)] # Vertical est le numéro de l'élément, horizontal est la capacité actuelle, dp content est la valeur maximale

for i in range(1, N+1):
    for j in range(1, W+1):
        
        if j-p[i][1] >= 0:
            dp[i][j] = max(dp[i-1][j],
                           dp[i-1][j-p[i][1]] + p[i][0])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][W])

C'est un typique du typique. Il semble y avoir un moyen d'écrire en dp unidimensionnel, mais c'est plus facile à écrire pour moi.

036. DPL_1_C -Problème de sac à dos

####Répondre

 N, W = map (int, input (). Split ()) # N est le type d'élément, W est le poids limite supérieur
 p = [(0, 0)] + [tuple (map (int, input (). split ())) for _ in range (N)] # (value, weight)
dp = [[0] * (W+1) for _ in range(N+1)]

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

        if j-p[i][1] >= 0:
            dp[i][j] = max(dp[i-1][j],
                           dp[i][j-p[i][1]] + p[i][0])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][W])

La différence avec le problème 35 est que vous pouvez sélectionner le même type de produit plus d'une fois, je ne modifierai donc le code que pour cette partie. En particulier,

dp[i][j] = max(dp[i-1][j],
               dp[i-1][j-p[i][1]] + p[i][0])

Quand

dp[i][j] = max(dp[i-1][j],
               dp[i][j-p[i][1]] + p[i][0])

alors,maxLe contenu est différent. Le problème 35 était sous la forme de "soustrayez le poids de celui avant l'indice i et ajoutez votre propre valeur", tandis que le problème 36 est "soustrayez votre propre poids et ajoutez votre propre valeur".

037. DPL_1_A -Problème de pièces

####Répondre

INF = float('inf')
n, m = map(int, input().split())
coins = [0] + list(map(int, input().split()))
dp = [[INF] * (n+1) for _ in range(m+1)]

dp[0][0] = 0

for i in range(1, m+1):
    for j in range(n+1):
        
        if j-coins[i] >= 0:
            dp[i][j] = min(dp[i-1][j-coins[i]] + 1,
                           dp[i][j-coins[i]] + 1,
                           dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[m][n])

Le problème des pièces est également typique, et l'idée est presque la même que celle du sac à dos.

038. ALDS_10_C -Sous-colonne commune la plus longue

####Répondre

# Je peux passer ça, mais je n'aime pas ça.
def main(A, B):
    dp = [0] * (len(B)+1)

    for a in A:
        before = dp[:]
        for j in range(1, len(B)+1):
            
            if a == B[j-1]:
                dp[j] = before[j-1] + 1
            elif dp[j] < dp[j-1]:
                dp[j] = dp[j-1]
                            
    return dp[-1]


if __name__ == "__main__":
    q = int(input())
    for _ in range(q):
        A = list(input())
        B = list(input())
        print(main(A, B))

Problème 34~Si vous l'écrivez de la même manière que 37, ce sera comme suit. J'aime cela car c'est le plus facile à écrire et il est également facile de restaurer la plus longue sous-chaîne commune. Cependant, sur le système, si vous écrivez comme suitTLEPar conséquent, la réponse ci-dessus a été faite en concevant diverses façons d'accélérer le processus.

# C'est TLE. La restauration est facile.
q = int(input())

answer_list = []
for _ in range(q):
    A = [''] + list(input())
    B = [''] + list(input())
    dp = [[0] * (len(B)) for _ in range(len(A))]

    for i in range(1, len(A)):
        for j in range(1, len(B)):
            
            if A[i] == B[j]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1],
                               dp[i-1][j])

    print(dp[len(A)-1][len(B)-1])

Surtout pour la lettre Afor i in range(1, len(A)):Par rapport au tournage avecfor a in A:Il semble qu'il soit plus rapide de faire demi-tour. Après tout, accéder à la liste avec des indices peut être assez lent.