n आइटम्स के वजन और मान दिए गए हैं; कार्य 0/1 नैपसैक के अनुसार आइटम्स को प्रिंट करना है निम्नलिखित वजन और मान के लिए W क्षमता के नैपसैक में, ताकि नैपसैक में अधिकतम कुल मान प्राप्त हो सके।
0/1 नैपसैक क्या है?
नैपसैक एक बैग की तरह है जिसका केवल एक निश्चित आकार होता है या एक बैग जो एक निश्चित मात्रा में वजन संभाल सकता है। नैपसैक में शामिल प्रत्येक आइटम का कुछ मान (लाभ) और कुछ वजन होता है। हमें उन वजनों को जोड़ना होगा जो हमें नैपसैक द्वारा धारण किए जा सकने वाले कुल वजन के अनुसार अधिकतम लाभ दिलाएंगे।
तो हमारे पास वजन, उनका मान (लाभ) और बैग का कुल वजन है जो एक नैपसैक धारण कर सकता है, तो 0/1 नैपसैक में हम केवल 1 और 0 का उल्लेख करते हैं उन आइटम्स के लिए जो शामिल हैं या नहीं जहां 0 उस आइटम के लिए है जिसे बैग में नहीं जोड़ा जा सकता, जबकि 1 उस आइटम के लिए है जिसे नैपसैक में शामिल किया जा सकता है।
एक सरल उदाहरण से समझते हैं:
मान लें val[] = {1, 2, 5, 6} // मान या लाभ
wt[] = {2, 3, 4, 5} // वजन
W = 8 // क्षमता
इसकी नैपसैक टेबल होगी:
knapsack.jpg
नैपसैक टेबल को निम्न सूत्र की मदद से भरा जा सकता है:
K[i, w] = max {K[i-1, w], K[i-1, w-wt[i]] + Val[i]}
बैकट्रैकिंग दृष्टिकोण का उपयोग करके टेबल को हल करना:
अब हमारे पास हर आइटम का डेटा है उनके लाभ और अधिकतम वजन के भीतर कुछ आइटम जोड़ने के बाद हम अधिकतम लाभ प्राप्त कर सकते हैं।
- k[n][w] से बैकट्रैकिंग शुरू करें, जहां k[n][w] 8 है।
- हम ऊपर की ओर जाएंगे जैसा कि नीला तीर उन सभी तरह से ऊपर निर्देशित करता है जहां काले तीर जा रहे हैं। तो 8 केवल 4th पंक्ति में है इसलिए हम 4th ऑब्जेक्ट को शामिल करेंगे, इसका मतलब है कि हमें 4th आइटम जोड़ने के बाद अधिकतम लाभ मिला।
- हम कुल लाभ यानी 8 को 4th आइटम जोड़कर प्राप्त लाभ यानी 6 से घटाएंगे तो हमें 2 मिलेगा।
- हम टेबल में बैकट्रैक करेंगे जब हमें 2 अधिकतम लाभ के रूप में मिलेगा। हमें यह तब मिला जब हम 2nd आइटम जोड़ते हैं।
- तो हम बैग को कुशलतापूर्वक भरने और अधिकतम लाभ प्राप्त करने के लिए नैपसैक में 2nd और 4th आइटम जोड़ेंगे।
उदाहरण
Input: val[] = {60, 100, 120}
wt[] = {10, 20, 30}
w = 50
Output: 220 //max value
30 20 //weights
Explanation: अधिकतम वजन यानी 50 तक पहुंचने के लिए हम दो वजन मान जोड़ेंगे, 30 जिसका मान 120 है और 20 जिसका मान 100 है
Input: val[] = {10, 40, 50}
wt[] = {2, 4, 5}
w = 6
Output: 50
4 2
Explanation: अधिकतम वजन यानी 6 तक पहुंचने के लिए हम दो वजन मान जोड़ेंगे, 4 जिसका मान 40 है और 2 जिसका मान 10 है।
एल्गोरिदम
Start
Step 1-> फंक्शन max(int a, int b) में
Return (a > b) ? a : b
Step 2-> फंक्शन printknapSack(int W, int wt[], int val[], int n) में
Declare 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-> फंक्शन 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; }
// W क्षमता के नैपसैक में रखे आइटम्स प्रिंट करता है
void printknapSack(int W, int wt[], int val[], int n) {
int i, w;
int K[n + 1][W + 1];
// टेबल K[][] को बॉटम-अप तरीके से बनाएं
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];
}
}
// नैपसैक का परिणाम स्टोर करता है
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];
}
}
}
// मुख्य कोड
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
