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

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

एल्गोरिदम

शुरुआत प्रत्येक आइटम का सेट इनपुट करें जिसमें वजन और मूल्य हो नैपसैक क्षमता सेट करें एक फ़ंक्शन बनाएं जो दो पूर्णांकों का अधिकतम लौटाता है। एक फ़ंक्शन बनाएं जो क्षमता 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] फ़ंक्शन को कॉल करें और प्रिंट करें। अंत

उदाहरण कोड

#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 << "नैपसैक में आइटम्स की संख्या दर्ज करें:";    int n, W;    cin >> n;    int v[n], w[n];    for (int i = 0; i < n; i++) {       cout << "आइटम " << i << " के लिए मूल्य और वजन दर्ज करें:";       cin >> v[i];       cin >> w[i];    }    cout << "नैपसैक की क्षमता दर्ज करें";    cin >> W;   cout << knapSack(W, w, v, n); return 0; }

आउटपुट

नैपसैक में आइटम्स की संख्या दर्ज करें:4 आइटम 0 के लिए मूल्य और वजन दर्ज करें:10 50 आइटम 1 के लिए मूल्य और वजन दर्ज करें:20 60 आइटम 2 के लिए मूल्य और वजन दर्ज करें:30 70 आइटम 3 के लिए मूल्य और वजन दर्ज करें:40 90 नैपसैक की क्षमता दर्ज करें100 40