01Dynamische Programmierung des Rucksackproblems

Die Grundidee der dynamischen Programmierung:

Dynamische Programmieralgorithmen werden normalerweise verwendet, um Probleme mit bestimmten optimalen Eigenschaften zu lösen, d. h. was wir normalerweise als optimale Unterstruktureigenschaften bezeichnen.

Der dynamische Programmieralgorithmus ähnelt der Divide-and-Conquer-Methode. Seine Grundidee besteht darin, das zu lösende Problem in mehrere Teilprobleme zu zerlegen, die Teilprobleme zuerst zu lösen und dann die Lösung zu erhalten aus den Lösungen dieser Teilprobleme zum ursprünglichen Problem. Der größte Unterschied zur Divide-and-Conquer-Methode besteht darin, dass bei Problemen, die zur Lösung durch dynamische Programmierung geeignet sind, die nach der Zerlegung erhaltenen Unterprobleme häufig nicht unabhängig voneinander sind, dh die Lösung der nächsten Unterstufe basiert auf der Lösung der vorherigen Unterstufe.

Wenn zur Lösung dieser Art von Problemen die Divide-and-Conquer-Methode verwendet wird, werden zu viele Unterprobleme zerlegt und einige Unterprobleme werden viele Male neu berechnet. Wenn wir die Antworten auf die gelösten Teilprobleme speichern und die erhaltenen Antworten bei Bedarf wiederfinden können, können wir viele wiederholte Berechnungen vermeiden und Zeit sparen. In einer Tabelle können wir die Antworten zu allen gelösten Teilproblemen festhalten. Unabhängig davon, ob das Teilproblem später verwendet wird, werden seine Ergebnisse in die Tabelle eingetragen, solange es berechnet wird.

Problembeschreibung:

Gegeben sind N Gegenstände und ein Rucksack. Das Gewicht des Gegenstands i ist Wi, sein Wert ist Vi und die Kapazität des Rucksacks ist C. Wie soll ich die Gegenstände auswählen, die ich in den Rucksack stecke, damit der Gesamtwert der in den Rucksack transportierten Gegenstände maximiert wird? ?

Bei der Auswahl der Artikel gibt es für jeden Artikel nur zwei Möglichkeiten, nämlich ihn in den Rucksack zu legen oder ihn nicht in den Rucksack zu stecken. Sie können Artikel i nicht mehrmals laden, noch können Sie nur einen Teil des Artikels laden. Daher wird dieses Problem als 0-1-Rucksackproblem bezeichnet.

Problemanalyse: V(i,j) stelle dar, dass die Kapazität, die in die ersten i(1<=i<=n) Elemente geladen werden kann, j(1<= j< ; = der Maximalwert der Elemente im Rucksack von C), kann die folgende dynamische Programmierfunktion erhalten werden:

(1)   V(i,0)=V(0,j)=0 

(2)   (a)  V(i,j)=V(i-1,j)    j<wi  

      (b)  V(i,j)=max{V(i-1,j) ,V(i-1,j-wi)+vi) }   j>wi

(1) Gleichung (1) zeigt, dass: wenn das Gewicht des i-ten Ist der Artikel größer als die Kapazität des Rucksacks, ist das Gewicht des i-ten Artikels größer als die Kapazität des Rucksacks. Der von Artikel i erhaltene Maximalwert ist derselbe wie der von i-1 Artikel vor dem Laden erhaltene Maximalwert , d. h. Artikel i kann nicht in den Rucksack geladen werden.

Gleichung (2) zeigt, dass es die folgenden zwei Situationen gibt, wenn das Gewicht des i-ten Gegenstands geringer ist als die Kapazität des Rucksacks: (a) Wenn der i-te Gegenstand nicht geladen ist in den Rucksack, dann der Wert der Gegenstände im Rucksack. Dies entspricht dem Wert, den man erhält, wenn man die ersten i-1 Gegenstände in einen Rucksack mit der Kapazität j steckt. (b) Wenn der i-te Artikel in den Rucksack gesteckt wird, ist der Wert des Rucksackartikels gleich dem Wert des i-1 Artikels im Rucksack mit der Kapazität j-wi plus dem Wert des i-ten Artikels vi ; Offensichtlich ist diejenige mit dem größten Wert die optimale Lösung, um die ersten i-Artikel in einen Rucksack mit einer Kapazität von j zu laden.

Empfohlenes Tutorial: PHP-Tutorial

Das obige ist der detaillierte Inhalt von01Dynamische Programmierung des Rucksackproblems. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!