So verwenden Sie den Rucksackproblem-Algorithmus in C++

So verwenden Sie den Rucksackproblem-Algorithmus in C++

Das Rucksackproblem ist eines der klassischen Probleme in Computeralgorithmen. Es geht darum, wie man einige Gegenstände auswählt, die unter einer bestimmten Rucksackkapazität in den Rucksack gesteckt werden sollen, sodass die Gesamtmenge Wert der Artikel maximieren. In diesem Artikel wird detailliert beschrieben, wie der dynamische Programmieralgorithmus in C++ zur Lösung des Rucksackproblems verwendet wird, und es werden spezifische Codebeispiele gegeben.

Zunächst müssen wir den Input und Output des Rucksackproblems definieren. Die Eingabe umfasst das Gewichtsarray wt[] des Artikels, das Wertearray val[] des Artikels und die Kapazität W des Rucksacks. Das Ergebnis besteht darin, auszuwählen, welche Gegenstände in den Rucksack gesteckt werden sollen, um den Wert zu maximieren. Es ist wie folgt definiert:

int knapSack(int W, int wt[], int val[], int n) {
   // 动态规划表格
   int dp[n+1][W+1];
  
   // 填充动态规划表格
   for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= W; j++) {
         if (i == 0 || j == 0)
            dp[i][j] = 0; // 边界条件
         else if (wt[i - 1] <= j)
            dp[i][j] = max(val[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i - 1][j]);
         else
            dp[i][j] = dp[i - 1][j];
      }
   }
  
   return dp[n][W]; // 返回最大价值
}

Im obigen Code verwenden wir ein zweidimensionales Array dp[][], um die Zustandsübergangstabelle der dynamischen Programmierung darzustellen, wobei dpi die Auswahl der ersten i Elemente und die Rucksackkapazität darstellt ist j Maximaler Gesamtwert. Der spezifische Algorithmus wird wie folgt implementiert:

1. Initialisieren Sie die erste Zeile und Spalte des zweidimensionalen Arrays dp[][] auf 0, um anzuzeigen, dass keine Elemente zur Auswahl stehen oder der maximale Gesamtwert bei einer Kapazität von 0 vorliegt ist 0;

2. Berechnen Sie ausgehend von Zeile 1 und Spalte 1 jeden dpi:

   • Wenn das Gewicht des aktuellen Artikels kleiner oder gleich der Rucksackkapazität j ist, können Sie Folgendes wählen: Legen Sie den Artikel hinein oder nicht. Wählen Sie den größten Gesamtwert in der Situation.
   • Wenn das Gewicht des aktuellen Artikels wt[i-1] größer ist als die Rucksackkapazität j, kann der aktuelle Artikel nicht hineingelegt werden in, und der Gesamtwert entspricht dem vorherigen Zustand, dpi-1;
3. Finally Gibt dpn zurück, was den maximalen Gesamtwert bei der Auswahl unter den ersten n Elementen darstellt und die Rucksackkapazität W beträgt.

Das Folgende ist ein Beispielcode, der den Rucksackproblemalgorithmus verwendet:

#include 
using namespace std;

int knapSack(int W, int wt[], int val[], int n) {
   // 动态规划表格
   int dp[n+1][W+1];
  
   // 填充动态规划表格
   for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= W; j++) {
         if (i == 0 || j == 0)
            dp[i][j] = 0; // 边界条件
         else if (wt[i - 1] <= j)
            dp[i][j] = max(val[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i - 1][j]);
         else
            dp[i][j] = dp[i - 1][j];
      }
   }
  
   return dp[n][W]; // 返回最大价值
}

int main() {
   int val[] = {60, 100, 120};
   int wt[] = {10, 20, 30};
   int W = 50;
   int n = sizeof(val) / sizeof(val[0]);
   cout << "最大总价值为：" << knapSack(W, wt, val, n) << endl;
   return 0;
}

Führen Sie den obigen Code aus und der maximale Gesamtwert des Ausgabeergebnisses beträgt 220, was bedeutet, dass bei einer Rucksackkapazität von 50 der maximale Wert sein kann erhalten Sie durch Auswahl der Punkte 1 und 3 Gesamtwert.

Zusätzlich zu den oben genannten dynamischen Programmiermethoden kann das Rucksackproblem auch mit anderen Methoden wie Backtracking und Greedy-Algorithmen gelöst werden. Das Obige ist eine detaillierte Einführung in die Verwendung des Rucksackproblemalgorithmus in C++. Ich hoffe, es wird Ihnen hilfreich sein.

Das obige ist der detaillierte Inhalt vonSo verwenden Sie den Rucksackproblem-Algorithmus in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!