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.
Value of items = {20, 25,40} Weights of items = {25, 20, 30} Capacity of the bag = 50
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.
#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; }
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!