Lösen Sie mit Python [100 frühere Fragen, die Anfänger und Fortgeschrittene lösen sollten] (034-038 Dynamische Planungsmethode: Knapsack DP basic)

1. Zweck

Lösen Sie 100 frühere Fragen, die Anfänger und Fortgeschrittene lösen sollten in Python. Das Ziel ist es, hellblau zu werden, wenn Sie alles gelöst haben.

Dieser Artikel ist "034-038 Dynamic Planning: Knapsack DP".

2. Zusammenfassung

dpHatte viel Ärger.bfs、dfsIch hatte viel Ärger, aber mehr als dasdpIch war besorgt, bis ich ein wenig verstand. Was ich getan habe, ist das gleiche wie für `BFS``` und` `DFS```. Während Sie die Erklärung lesen, debuggen Sie jede Zeile, bis Sie das Antwortbeispiel von` AC verstehen. Ich folge dir einfach. Außerdem konnte ich zunächst keine `` `DP von 100 sorgfältig ausgewählten Fragen beantworten, also habe ich zuerst Typischer DP-Wettbewerb`` A ~ L ausprobiert Nachdem ich bis zu ``gelöst hatte (oder besser gesagt, ich habe es verstanden, als ich mir das Antwortbeispiel angesehen hatte), fing ich an. Dann konnte ich es ein wenig lösen.

3. Hauptgeschichte

034 --038 Dynamische Planungsmethode: Knapsack DP basic

034. ALDS_10_A - Anzahl der Fibonacci

Antworten

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])

Wenn Sie es rekursiv wie unten schreibenTLEWeil es nicht geht``DP```Es ist ein Problem, mit dem Sie sehen können, dass Sie es lösen müssen.

# Das ist 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 Rucksackproblem

####Antworten

 N, W = map (int, input (). Split ()) # N Elemente, W ist die Gewichtskapazität
 p = [(0, 0)] + [Tupel (map (int, input (). split ())) für _ im Bereich (N)] # Goods-> (Value, Weight)
 dp = [[0] * (W + 1) für _ im Bereich (N + 1)] # Vertikal ist die Artikelnummer, horizontal ist die aktuelle Kapazität, dp-Inhalt ist der Maximalwert

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])

Es ist typisch für das Typische. Es scheint eine Möglichkeit zu geben, in eindimensionalem dp zu schreiben, aber das ist für mich einfacher zu schreiben.

036. DPL_1_C -Rucksackproblem

####Antworten

 N, W = map (int, input (). Split ()) # N ist der Elementtyp, W ist das obere Grenzgewicht
 p = [(0, 0)] + [Tupel (map (int, input (). split ())) für _ im Bereich (N)] # (Wert, Gewicht)
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])

Der Unterschied zu Problem 35 besteht darin, dass Sie denselben Produkttyp mehrmals auswählen können, sodass ich den Code nur für diesen Teil ändern werde. Speziell,

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

Wann

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

damit,maxDer Inhalt ist unterschiedlich. Problem 35 bestand in der Form "Subtrahieren Sie das Gewicht von dem vor dem Index i und addieren Sie Ihren eigenen Wert", während Problem 36 "Subtrahieren Sie Ihr eigenes Gewicht und addieren Sie Ihren eigenen Wert" ist.

037. DPL_1_A -Münzproblem

####Antworten

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])

Das Münzproblem ist ebenfalls typisch und die Idee ist fast dieselbe wie beim Rucksack.

038. ALDS_10_C -Längste gemeinsame Unterspalte

####Antworten

# Ich kann das bestehen, aber ich mag es nicht.
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))

Problem 34~Wenn Sie es auf die gleiche Weise wie 37 schreiben, wird es wie folgt sein. Ich mag das, weil es am einfachsten zu schreiben ist und es auch einfach ist, den längsten gemeinsamen Teilstring wiederherzustellen. Auf dem System jedoch, wenn Sie wie folgt schreibenTLEDaher wurde die obige Antwort gegeben, indem verschiedene Wege entwickelt wurden, um den Prozess zu beschleunigen.

# Das ist TLE. Die Wiederherstellung ist einfach.
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])

Speziell für Buchstabe A.for i in range(1, len(A)):Im Vergleich zum Drehen mitfor a in A:Es scheint, dass es schneller ist, es umzudrehen. Schließlich kann der Zugriff auf die Liste mit Indizes recht langsam sein.