Übersetzen Sie in der Sprache C Folgendes ins Chinesische: 0-1 Rucksackproblem

Ein Rucksack ist eine Tasche. Beim Rucksackproblem hingegen geht es darum, Gegenstände entsprechend ihrem Wert in Taschen zu packen. Sein Ziel ist es, den Wert innerhalb der Tasche zu maximieren. In einem 0-1-Rucksack können Sie wählen, ob Sie einen Gegenstand hineinlegen oder wegwerfen möchten. Es gibt kein Konzept, einen Teil eines Gegenstands in den Rucksack zu stecken.

Beispielproblem

Value of items = {20, 25,40}
Weights of items = {25, 20, 30}
Capacity of the bag = 50

Gewichtsverteilung

25,20{1,2}
20,30 {2,3}
If we use {1,3} the weight will be above the max allowed value.
For {1,2} : weight= 20+25=45 Value = 20+25 = 45
For {2,3}: weight=20+30=50 Value = 25+40=65

Der Maximalwert beträgt 65, also legen wir die Artikel 2 und 3 in den Rucksack.

0-1 Rucksackproblemprogramm

#include<stdio.h>
int max(int a, int b) {
   if(a>b){
      return a;
   } else {
      return b;
   }
}
int knapsack(int W, int wt[], int val[], int n) {
   int i, w;
   int knap[n+1][W+1];
   for (i = 0; i <= n; i++) {
      for (w = 0; w <= W; w++) {
         if (i==0 || w==0)
            knap[i][w] = 0;
         else if (wt[i-1] <= w)
            knap[i][w] = max(val[i-1] + knap[i-1][w-wt[i-1]], knap[i-1][w]);
         else
            knap[i][w] = knap[i-1][w];
      }
   }
   return knap[n][W];
}
int main() {
   int val[] = {20, 25, 40};
   int wt[] = {25, 20, 30};
   int W = 50;
   int n = sizeof(val)/sizeof(val[0]);
   printf("The solution is : %d", knapsack(W, wt, val, n));
   return 0;
}

Ausgabe

The solution is : 65

Das obige ist der detaillierte Inhalt vonÜbersetzen Sie in der Sprache C Folgendes ins Chinesische: 0-1 Rucksackproblem. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!