Heim > Backend-Entwicklung > C++ > Hauptteil

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

WBOY
Freigeben: 2023-09-03 11:17:06
nach vorne
1235 Leute haben es durchsucht

Ü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
Nach dem Login kopieren

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
Nach dem Login kopieren

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;
}
Nach dem Login kopieren

Ausgabe

The solution is : 65
Nach dem Login kopieren

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!

Verwandte Etiketten:
Quelle:tutorialspoint.com
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage