C++ प्रोग्राम: फ्रैक्शनल नैपसैक समस्या हल करना

फ्रैक्शनल नैपसैक समस्या में, आइटम्स का एक सेट दिया जाता है, प्रत्येक का एक वजन और एक वैल्यू होती है। हमें नैपसैक की कुल वैल्यू को अधिकतम करने के लिए आइटम्स को तोड़ने की आवश्यकता होती है और यह लालची दृष्टिकोण (ग्रेडी अप्रोच) से किया जा सकता है।

एल्गोरिदम

Begin
    Item स्ट्रक्चर का ऐरे लें
    वैल्यू, वजन, नैपसैक वजन और डेंसिटी घोषित करें
    प्रत्येक आइटम के लिए डेंसिटी = वैल्यू/वजन की गणना करें
    घटती डेंसिटी के क्रम में आइटम्स ऐरे को सॉर्ट करें
    हम ऐरे के टॉप से वैल्यू जोड़ते हैं जब तक बैग भर न जाए, यानी कुल वैल्यू <= W
End

उदाहरण कोड

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

typedef struct {
    int v;
    int w;
    float d;
} Item;

void input(Item items[], int sizeOfItems) {
    cout << "Enter total " << sizeOfItems << " item's values and weight" << endl;
    for (int i = 0; i < sizeOfItems; i++) {
        cout << "Enter " << i + 1 << " V ";
        cin >> items[i].v;
        cout << "Enter " << i + 1 << " W ";
        cin >> items[i].w;
    }
}

void display(Item items[], int sizeOfItems) {
    int i;
    cout << "values: ";
    for (i = 0; i < sizeOfItems; i++) {
        cout << items[i].v << "\t";
    }
    cout << endl << "weight: ";
    for (i = 0; i < sizeOfItems; i++) {
        cout << items[i].w << "\t";
    }
    cout << endl;
}

bool compare(Item i1, Item i2) {
    return (i1.d > i2.d);
}

float knapsack(Item items[], int sizeOfItems, int W) {
    int i, j;
    float totalValue = 0, totalWeight = 0;
    for (i = 0; i < sizeOfItems; i++) {
        items[i].d = (float)items[i].v / items[i].w; // टाइपकास्टिंग की गई (v इंट है और w भी इंट है इसलिए d का अंतिम मान इंट के रूप में मिलता है)
    }
    sort(items, items + sizeOfItems, compare);
    
    for (i = 0; i < sizeOfItems; i++) {
        if (totalWeight + items[i].w <= W) {
            totalValue += items[i].v;
            totalWeight += items[i].w;
        } else {
            int wt = W - totalWeight;
            totalValue += (wt * items[i].d);
            totalWeight += wt;
            break;
        }
    }
    cout << "Total weight in bag " << totalWeight << endl;
    return totalValue;
}

int main() {
    int W;
    Item items[4];
    input(items, 4);
    cout << "Entered data \n";
    display(items, 4);
    cout << "Enter Knapsack weight \n";
    cin >> W;
    float mxVal = knapsack(items, 4, W);
    cout << "Max value for " << W << " weight is " << mxVal;
}

आउटपुट

Enter total 4 item's values and weight
Enter 1 V
Enter 1 W
Enter 2 V
Enter 2 W
Enter 3 V
Enter 3 W
Enter 4 V
Enter 4 W
Entered data
values: 2      0      0      0
weight: 0      490642064 0      4196544
Enter Knapsack weight
Total weight in bag 0
Max value for 0 weight is 2