n वस्तुओं के भार और मान दिए गए हैं; कार्य क्षमता W के एक नैपसैक में निम्नलिखित वज़न और मानों के लिए 0/1 knapsack के अनुसार आइटम प्रिंट करना है, ताकि knapsack में अधिकतम कुल मान प्राप्त किया जा सके।
0/1 बस्ता क्या है?
नैपसैक एक निश्चित आकार या एक बैग के साथ एक बैग की तरह है जो एक निश्चित मात्रा में वजन को संभाल सकता है। थैले में शामिल प्रत्येक वस्तु का कुछ मूल्य (लाभ) और कुछ वजन होता है। हमें उन भारों को जोड़ना होगा जो हमें एक थैले के कुल भार के अनुसार अधिकतम लाभ दिलाएंगे।
तो हमारे पास वजन, उनका मूल्य (लाभ) और बैग का कुल वजन है जिसे एक थैला पकड़ सकता है, इसलिए 0/1 नैपसैक में हम केवल 1 और 0 का उल्लेख उस आइटम के लिए करते हैं जो शामिल है या नहीं जहां 0 उस आइटम के लिए है जो कर सकता है' t को बैग में जोड़ा जाना चाहिए, जबकि 1 उस वस्तु के लिए है जिसे थैले में शामिल किया जा सकता है।
आइए एक साधारण उदाहरण की सहायता से समझते हैं -
Let us assume val[] = {1, 2, 5, 6}//value or profit
wt[] = {2, 3, 4, 5}//weight
W = 8//Capacity इसकी नैपसैक टेबल होगी -
knapsack.jpg
Knapsack तालिका को निम्न सूत्र की सहायता से भरा जा सकता है -
K [i ,w] =अधिकतम {K [i−1, w], K [i−1, w−wt [i]] + Val[i]}
बैकट्रैकिंग दृष्टिकोण का उपयोग करके तालिका को हल करना,
अब हमारे पास प्रत्येक वस्तु का डेटा उनके मुनाफे और अधिकतम वजन के भीतर अधिकतम लाभ है जो हम कुछ वस्तुओं को जोड़ने के बाद प्राप्त कर सकते हैं।
- बैकट्रैकिंग फॉर्म k[n][w] शुरू करें, जहां k[n][w] 8 है।
- हम ऊपर की दिशा में जाएंगे क्योंकि नीला तीर ऊपर की ओर जाता है जहां काले तीर जा रहे हैं। तो 8 केवल चौथी पंक्ति में है इसलिए हम चौथी वस्तु को शामिल करेंगे, इसका मतलब है कि हमें चौथी वस्तु जोड़ने के बाद अधिकतम लाभ मिला।
- हम कुल लाभ को घटा देंगे जो कि 8 है, चौथी वस्तु को जोड़ने पर प्राप्त लाभ के साथ, यानी 6 हमें 2 मिलेगा।
- जब हम अधिकतम लाभ के रूप में 2 प्राप्त करते हैं, तो हम यह देखने के लिए तालिका को पीछे कर देंगे। हमें यह तब मिला जब हम दूसरा आइटम जोड़ते हैं
- इसलिए हम बैग को कुशलतापूर्वक भरने और अधिकतम लाभ प्राप्त करने के लिए एक थैले में दूसरा और चौथा आइटम जोड़ देंगे।
उदाहरण
Input: val[] = {60, 100, 120}
wt[] = {10, 20, 30}
w = 50
Output: 220 //max value
30 20 //weights
Explanation: to reach till the maximum weight i.e. 50 we will add two weights value,
30 whose value is 120 and 20 whose value is 100
Input: val[] = {10, 40, 50}
wt[] = {2, 4, 5}
w = 6
Output: 50
4 2
Explanation: to reach till the maximum weight i.e. 6 we will add two weights value, 4
whose value is 40 and 2 whose value is 10. एल्गोरिदम
Start
Step 1-> In function max(int a, int b)
Return (a > b) ? a : b
Step 2-> In function printknapSack(int W, int wt[], int val[], int n)
Decalare i, w, K[n + 1][W + 1]
Loop For i = 0 and i <= n and i++
Loop For w = 0 and w <= W and w++
If i == 0 || w == 0 then,
Set K[i][w] = 0
Else If wt[i - 1] <= w then,
Set K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
Else
Set K[i][w] = K[i - 1][w]
Set res = K[n][W]
Print res
Set w = W
Loop For i = n and i > 0 && res > 0 and i--
If res == K[i - 1][w] then,
Continue
Else {
Print wt[i - 1])
Set res = res - val[i - 1]
Set w = w - wt[i - 1]
Step 3-> In function int main()
Set val[] = { 50, 120, 70 }
Set wt[] = { 10, 20, 30 }
Set W = 50
Set n = sizeof(val) / sizeof(val[0])
Call function printknapSack(W, wt, val, n)
Stop उदाहरण
#include <bits/stdc++.h>
int max(int a, int b) { return (a > b) ? a : b; }
// Prints the items which are put in a knapsack of capacity W
void printknapSack(int W, int wt[], int val[], int n) {
int i, w;
int K[n + 1][W + 1];
// Build table K[][] in bottom up manner
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = max(val[i - 1] +
K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
// stores the result of Knapsack
int res = K[n][W];
printf("maximum value=%d\n", res);
w = W;
printf("weights included\n");
for (i = n; i > 0 && res > 0; i--) {
if (res == K[i - 1][w])
continue;
else {
printf("%d ", wt[i - 1]);
res = res - val[i - 1];
w = w - wt[i - 1];
}
}
}
// main code
int main() {
int val[] = { 50, 120, 70 };
int wt[] = { 10, 20, 30 };
int W = 50;
int n = sizeof(val) / sizeof(val[0]);
printknapSack(W, wt, val, n);
return 0;
} आउटपुट
maximum value=190 weights included 30 20