0-1 नैपसैक समस्या में, आइटम्स का एक सेट दिया जाता है, प्रत्येक का एक वजन और एक वैल्यू होती है। हमें प्रत्येक आइटम की संख्या निर्धारित करने की आवश्यकता होती है जिसे एक संग्रह में शामिल किया जाए ताकि कुल वजन दी गई सीमा से कम या बराबर हो और कुल वैल्यू जितना संभव हो उतना बड़ा हो।
इनपुट
Value = [10, 20, 30, 40, 60, 70] Weight = [1, 2, 3, 6, 7, 4] int w = 7
आउटपुट
knapsack value is: 100
एल्गोरिदम
Begin इनपुट: प्रत्येक का वजन और वैल्यू वाले आइटम्स का सेट नैपसैक क्षमता सेट करें आइटम्स की संख्या = sizeof(values) / sizeof(values[0]) Knapsack(Values (ऐरे v में स्टोर्ड), Weights (ऐरे w में स्टोर्ड), अलग-अलग आइटम्स की संख्या (n), नैपसैक क्षमता W) यदि (w < 0) लौटाएं यदि कोई आइटम नहीं बचा या क्षमता 0 हो गई तो 0 लौटाएं वर्तमान आइटम n को नैपसैक में शामिल करें (v[n]) और शेष आइटम्स (n - 1) के लिए घटती क्षमता (W - w[n]) के साथ रिकर्स करें वर्तमान आइटम n को नैपसैक से बाहर रखें और शेष आइटम्स (n - 1) के लिए रिकर्स करें वर्तमान आइटम को शामिल या बाहर करके प्राप्त अधिकतम वैल्यू लौटाएं End
उदाहरण कोड
#include <iostream>
#include <climits>
using namespace std;
int knapSack(int v[], int w[], int n, int W) {
if (W < 0)
return INT_MIN;
if (n < 0 || W == 0)
return 0;
int in = v[n] + knapSack(v, w, n - 1, W - w[n]);
int ex = knapSack(v, w, n - 1, W);
return max(in, ex);
}
int main() {
int v[] = { 10, 20, 30, 40, 60, 70 };
int w[] = { 1, 2, 3, 6, 7, 4 };
int W = 7;
int n = sizeof(v) / sizeof(v[0]);
cout << "Knapsack value is " << knapSack(v, w, n - 1, W);
return 0;
}
आउटपुट
Knapsack value is 100