एक थैला एक थैला है। और बस्ता समस्या वस्तुओं के मूल्य के आधार पर बैग में सामान डालने से संबंधित है। इसका उद्देश्य बैग के अंदर मूल्य को अधिकतम करना है। 0-1 Knapsack में आप या तो वस्तु रख सकते हैं या त्याग सकते हैं, सामान के कुछ भाग को थैले में डालने की कोई अवधारणा नहीं है।
नमूना समस्या
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 अधिकतम मान 65 है इसलिए हम आइटम 2 और 3 को थैले में डाल देंगे।
0-1 KNAPSACK समस्या के लिए कार्यक्रम
#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