Wie löst man das Rucksackproblem in PHP mithilfe eines dynamischen Programmieralgorithmus und erhält die optimale Lösung?

Wie verwende ich einen dynamischen Programmieralgorithmus, um das Rucksackproblem in PHP zu lösen und die optimale Lösung zu erhalten?

Das Rucksackproblem ist eines der klassischen kombinatorischen Optimierungsprobleme in der Informatik. Angesichts einer Reihe von Gegenständen und des Fassungsvermögens eines Rucksacks ist die Frage, wie man Gegenstände auswählt, die in den Rucksack gesteckt werden sollen, um den Gesamtwert der Gegenstände im Rucksack zu maximieren, der Kern des Rucksackproblems, das gelöst werden muss.

Dynamische Programmierung ist eine der gängigen Methoden zur Lösung des Rucksackproblems. Die optimale Lösung erhält man schließlich durch die Aufteilung des Problems in Teilprobleme und das Speichern der Lösungen für die Teilprobleme. Im Folgenden erklären wir im Detail, wie man den dynamischen Programmieralgorithmus verwendet, um das Rucksackproblem in PHP zu lösen.

Zuerst müssen wir die Eingabe und Ausgabe des Rucksackproblems definieren:

Eingabe:

• Das Gewichtsarray der Elemente $weights, $weights[$i] repräsentiert das Gewicht des $i-ten Elements
• Das Wertarray der Elemente $values, $values[$i] repräsentiert den Wert des $i-ten Elements
• Die Kapazität des Rucksacks $capacity stellt die maximale Kapazität des Rucksacks dar

Ausgabe:

• The Maximaler Gesamtwert der Gegenstände im Rucksack

Als nächstes müssen wir ein zweidimensionales Array $dp definieren, um die Lösung des Unterproblems zu speichern. $dp[$i][$j] stellt den maximalen Gesamtwert der ersten $i Artikel dar, wenn die Rucksackkapazität $j beträgt.

Der Ablauf des Algorithmus ist wie folgt:

1. Initialisieren Sie das $dp-Array und setzen Sie alle Elemente auf 0.

2. Die äußere Schleife durchläuft den Index des Artikels, von $i = 1 bis $i = count($weights) - 1:

   • Die innere Schleife durchläuft die Kapazität des Rucksacks, von $j = 0 bis $j = $ Kapazität:

     • Wenn das Gewicht des aktuellen Artikels $weights[$i] größer ist als die Kapazität des Rucksacks $j, dann ist $dp[$i][$j] = $dp[$i - 1][$j], das heißt, die aktuellen Artikel können nicht in den Rucksack gelegt werden und der maximale Gesamtwert ist derselbe wie die ersten $i - 1 Artikel.
     • Andernfalls kann der aktuelle Artikel in den Rucksack gelegt werden und der von ihm generierte Wert $values[$i] plus dem maximalen Gesamtwert vor dem Platzieren des Artikels $dp[$i - 1][$j - $weights[$ i ]] Nehmen Sie im Vergleich zum aktuellen Wert den größeren Wert als $dp[$i][$j].
3. Gibt $dp[count($weights) - 1][$capacity] zurück, was den maximalen Gesamtwert der ersten count($weights)-Elemente darstellt, wenn die Rucksackkapazität $capacity beträgt.

Das Folgende ist ein dynamischer Programmieralgorithmus, der PHP-Code verwendet, um das Rucksackproblem zu implementieren:

function knapsack($weights, $values, $capacity) {
    $dp = [];
    for ($i = 0; $i < count($weights); $i++) {
        $dp[$i] = [];
        for ($j = 0; $j <= $capacity; $j++) {
            $dp[$i][$j] = 0;
        }
    }
    
    for ($i = 1; $i < count($weights); $i++) {
        for ($j = 0; $j <= $capacity; $j++) {
            if ($weights[$i] > $j) {
                $dp[$i][$j] = $dp[$i - 1][$j];
            } else {
                $dp[$i][$j] = max($dp[$i - 1][$j], $values[$i] + $dp[$i - 1][$j - $weights[$i]]);
            }
        }
    }
    
    return $dp[count($weights) - 1][$capacity];
}

Mit dem obigen Code können wir das Rucksackproblem lösen, indem wir die Funktion knapsack($weights, $values, $capacity) aufrufen und die optimale Lösung erhalten.

Ich hoffe, dieser Artikel kann Ihnen helfen zu verstehen, wie Sie mithilfe eines dynamischen Programmieralgorithmus das Rucksackproblem in PHP lösen und die optimale Lösung erhalten.

Das obige ist der detaillierte Inhalt vonWie löst man das Rucksackproblem in PHP mithilfe eines dynamischen Programmieralgorithmus und erhält die optimale Lösung?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!