फ्रैक्शनल नैपसैक प्रॉब्लम

आइटम्स की एक लिस्ट दी गई है, प्रत्येक आइटम का अपना वैल्यू और वजन है। आइटम्स को एक नैपसैक में रखा जा सकता है जिसकी अधिकतम वजन सीमा W है। समस्या यह है कि ऐसा वजन ढूंढें जो W से कम या बराबर हो, और वैल्यू अधिकतम हो।

नैपसैक प्रॉब्लम के दो प्रकार हैं।

• 0 – 1 नैपसैक
• फ्रैक्शनल नैपसैक

0 – 1 नैपसैक के लिए, आइटम्स को छोटे टुकड़ों में विभाजित नहीं किया जा सकता, और फ्रैक्शनल नैपसैक के लिए, आइटम्स को छोटे टुकड़ों में तोड़ा जा सकता है।

यहां हम फ्रैक्शनल नैपसैक प्रॉब्लम पर चर्चा करेंगे।

इस एल्गोरिदम की टाइम कॉम्प्लेक्सिटी O(n Log n) है।

इनपुट और आउटपुट

इनपुट: अधिकतम वजन = 50। वैल्यू और वजन के साथ आइटम्स की लिस्ट।
{(60, 10), (100, 20), (120, 30)}
आउटपुट: अधिकतम वैल्यू: 240
वजन 20 और 30 के आइटम्स लेकर

एल्गोरिदम

fractionalKnapsack(weight, itemList, n)

इनपुट: नैपसैक का अधिकतम वजन, आइटम्स की लिस्ट और आइटम्स की संख्या
आउटपुट: प्राप्त अधिकतम वैल्यू।

Begin
    वैल्यू और वजन के अनुपात के आधार पर आइटम लिस्ट को सॉर्ट करें
    currentWeight := 0
    knapsackVal := 0
    for all items i in the list do
        if currentWeight + weight of item[i] < weight then
            currentWeight := currentWeight + weight of item[i]
            knapsackVal := knapsackVal + value of item[i]
        else
            remaining := weight - currentWeight
            knapsackVal = knapsackVal + value of item[i] * (remaining / weight of item[i])
            break the loop
        done
    done
End

उदाहरण

#include <iostream>
#include <algorithm>
using namespace std;

struct item {
    int value, weight;
};

bool cmp(struct item a, struct item b) {
    // आइटम a और आइटम b की तुलना वैल्यू और वजन के अनुपात के आधार पर करें
    double aRatio = (double)a.value / a.weight;
    double bRatio = (double)b.value / b.weight;
    return aRatio > bRatio;
}

double fractionalKnapsack(int weight, item itemList[], int n) {
    sort(itemList, itemList + n, cmp); // तुलना फंक्शन का उपयोग करके आइटम लिस्ट सॉर्ट करें
    int currWeight = 0; // नैपसैक में वर्तमान वजन
    double knapsackVal = 0.0;
    for (int i = 0; i < n; i++) {
        // सभी आइटम्स के माध्यम से चेक करें
        if (currWeight + itemList[i].weight <= weight) {
            // जब चयनित आइटम के लिए पर्याप्त जगह हो, तो इसे जोड़ें
            currWeight += itemList[i].weight;
            knapsackVal += itemList[i].value;
        } else {
            // जब पूरे आइटम के लिए जगह न हो, तो इसे छोटे भागों में तोड़ें
            int remaining = weight - currWeight;
            knapsackVal += itemList[i].value * ((double) remaining / itemList[i].weight);
            break;
        }
    }
    return knapsackVal;
}

int main() {
    int weight = 50; // नैपसैक का वजन
    item itemList[] = {{60, 10}, {100, 20}, {120, 30}};
    int n = 3;
    cout << "अधिकतम वैल्यू: " << fractionalKnapsack(weight, itemList, n);
}

आउटपुट

अधिकतम वैल्यू: 240