C++ प्रोग्राम डायनेमिक प्रोग्रामिंग का उपयोग करके नैकपैक समस्या को हल करने के लिए

यह गतिशील प्रोग्रामिंग का उपयोग करके 0-1 knapsack समस्या को हल करने के लिए एक C++ प्रोग्राम है। 0-1 बस्ता समस्या में, वस्तुओं का एक सेट दिया जाता है, प्रत्येक का एक वजन और एक मूल्य होता है। हमें संग्रह में शामिल करने के लिए प्रत्येक आइटम की संख्या निर्धारित करने की आवश्यकता है ताकि कुल वजन दी गई सीमा से कम या उसके बराबर हो और कुल मूल्य जितना संभव हो उतना बड़ा हो।

एल्गोरिदम

Begin
Input set of items each with a weight and a value
Set knapsack capacity
Create a function that returns maximum of two integers.
Create a function which returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int w[], int v[], int n)
int i, wt;
int K[n + 1][W + 1]
for i = 0 to n
for wt = 0 to W
if (i == 0 or wt == 0)
   Do K[i][wt] = 0
else if (w[i - 1] <= wt)
   Compute: K[i][wt] = max(v[i - 1] + K[i - 1][wt - w[i - 1]], K[i -1][wt])
else
   K[i][wt] = K[i - 1][wt]
   return K[n][W]
   Call the function and print.
End

उदाहरण कोड

#include <iostream>
using namespace std;
int max(int x, int y) {
   return (x > y) ? x : y;
}
int knapSack(int W, int w[], int v[], int n) {
   int i, wt;
   int K[n + 1][W + 1];
   for (i = 0; i <= n; i++) {
      for (wt = 0; wt <= W; wt++) {
         if (i == 0 || wt == 0)
         K[i][wt] = 0;
         else if (w[i - 1] <= wt)
            K[i][wt] = max(v[i - 1] + K[i - 1][wt - w[i - 1]], K[i - 1][wt]);
         else
        K[i][wt] = K[i - 1][wt];
      }
   }
   return K[n][W];
}
int main() {
   cout << "Enter the number of items in a Knapsack:";
   int n, W;
   cin >> n;
   int v[n], w[n];
   for (int i = 0; i < n; i++) {
      cout << "Enter value and weight for item " << i << ":";
      cin >> v[i];
      cin >> w[i];
   }
   cout << "Enter the capacity of knapsack";
   cin >> W;
   cout << knapSack(W, w, v, n);
   return 0;
}

आउटपुट

Enter the number of items in a Knapsack:4
Enter value and weight for item 0:10
50
Enter value and weight for item 1:20
60
Enter value and weight for item 2:30
70
Enter value and weight for item 3:40
90
Enter the capacity of knapsack100
40