Wie kann ich eine Lösung mit dynamischer Programmierung schreiben?

Question

Derzeit versuchen, dieses Problem aus interactivepython.org zu lösen:

Angenommen, Sie ein Informatiker/Kunstdieb sind, die in eine große Kunstgalerie gebrochen hat. Alles, was du bei dir hast, um deine gestohlene Kunst herauszuholen, ist dein Rucksack, der nur W Pounds von Kunst enthält, aber für jedes Kunstwerk weißt du seinen Wert und sein Gewicht. Schreiben Sie eine dynamische Programmierfunktion, um Ihren Gewinn zu maximieren.

Mein erster Gedanke war, den maximalen Wert aller Gegenstände zu finden, subtrahiert, das Gewicht dieses Elements aus dem maximalen Gewicht, dann den Maximalwert aller Elemente mit dem neuen Maximalgewicht als Einschränkung finden. Schnell wurde mir klar, dass das nicht funktionieren würde.

Jede Hilfe, wie man dies mit dynamischer Programmierung angehen könnte, wäre willkommen.

Answer 1

Das Problem, dem Sie gegenüberstehen, wird 0-1 knapsack problem genannt.

Angenommen, Sie haben einen Rucksack haben (mit max. Cap. W) von n Elemente, die jeweils mit dem Wert v und Gewicht w.
Sie möchten so viel "Wert" wie möglich einpacken, während Sie nicht mehr Gewicht als W tragen können.

Da es eine dynamische Programmierung Ansatz ist, verwenden wir ein Array dp [] [], um unsere Antwort zu berechnen.

Zuerst füllen unsere dynamische Programmierung Matrix mit Nullen:

for i in range(0,W): 
    dp[0, i] = 0 

Dann:

for i in range(1, n): # for each item 
    for j in range(0, W): # till max capacity 
    if w[i] > j then: 
     dp[i,j] = dp[i-1,j] # too heavy item, leave it 
    else: 
     dp[i,j] = max(dp[i-1, j], dp[i-1, j-w[i]] + v[i]) # add it 

Danach wird das Ergebnis, das Sie sollten in dp [n] [W] der Lage sein, erwarten Zelle.

---

Es gibt viele Optimierungen für diesen Algorithmus (sowie ein Original/Voll Knapsackproblems), aber da man nicht einmal schreiben haben, was haben Sie versucht, so weit oder u nicht, ich werde verlassen du damit. Viel Glück.