नैपसैक एक बैग है। और नैपसैक समस्या वस्तुओं को उनके मूल्य के आधार पर बैग में रखने से संबंधित है। इसका उद्देश्य बैग के अंदर मूल्य को अधिकतम करना है। 0-1 नैपसैक में आप या तो वस्तु रख सकते हैं या छोड़ सकते हैं, वस्तु के किसी हिस्से को रखने की अवधारणा नहीं है।
नमूना समस्या
वस्तुओं के मूल्य = {20, 25, 40}
वस्तुओं के वजन = {25, 20, 30}
बैग की क्षमता = 50
वजन वितरण
25,20 {1,2} 20,30 {2,3}
यदि हम {1,3} उपयोग करते हैं तो वजन अधिकतम अनुमत मान से ऊपर होगा।
{1,2} के लिए: वजन = 20+25=45, मूल्य = 20+25=45
{2,3} के लिए: वजन = 20+30=50, मूल्य = 25+40=65
अधिकतम मूल्य 65 है इसलिए हम वस्तु 2 और 3 को नैपसैक में रखेंगे।
0-1 नैपसैक समस्या का प्रोग्राम
#include <stdio.h>
int max(int a, int b) {
return (a > b) ? a : 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
