विचार यह है कि ग्रेडी दृष्टिकोण फ्रैक्शनल नैपसैक समस्या के लिए सर्वोत्तम समाधान प्रदान करता है।
यह जांचने के लिए कि कोई विशेष नोड हमें बेहतर समाधान दे सकता है या नहीं, हम ग्रेडी दृष्टिकोण लागू करके नोड के माध्यम से इष्टतम समाधान की गणना करते हैं। यदि ग्रेडी दृष्टिकोण द्वारा गणना किया गया समाधान स्वयं अब तक के सर्वोत्तम से अधिक है, तो हम नोड के माध्यम से बेहतर समाधान प्राप्त नहीं कर सकते।
पूर्ण एल्गोरिदम नीचे दिया गया है -
वैल्यू प्रति यूनिट वेट के अनुपात के घटते क्रम के अनुसार सभी आइटम्स को सॉर्ट करें ताकि ग्रेडी दृष्टिकोण लागू करके एक ऊपरी सीमा की गणना की जा सके।
अधिकतम लाभ इनिशियलाइज़ करें, जैसे maxProfit = 0
एक खाली क्यू Q बनाई जाती है।
निर्णय ट्री का एक डमी नोड बनाया जाता है और Q में एन्क्यू किया जाता है। डमी नोड का लाभ और वजन 0 हो।
निम्नलिखित करें जब तक Q खाली नहीं है।
Q से एक आइटम निकालें। मान लीजिए निकाला गया आइटम u है।
अगले लेवल नोड का लाभ कैलकुलेट करें। यदि लाभ maxProfit से अधिक है, तो maxProfit को अपडेट करें।
अगले लेवल नोड की बाउंड कैलकुलेट करें। यदि बाउंड maxProfit से अधिक है, तो अगले लेवल नोड को Q में जोड़ें।
उस मामले पर विचार करें जब अगले लेवल नोड को समाधान के हिस्से के रूप में नहीं माना जाता है और लेवल को अगले के रूप में लेकिन वजन और लाभ को अगले लेवल नोड्स पर विचार किए बिना क्यू में एक नोड जोड़ें।
नीचे चित्रण दिए गए हैं -
इनपुट
// प्रत्येक जोड़ी में पहली चीज आइटम का वजन है
// और दूसरी चीज आइटम का मूल्य है
Item arr1[] = {{2, 40}, {3.14, 50}, {1.98, 100}, {5, 95}, {3, 30}};
Knapsack Capacity W1 = 10
आउटपुट
The maximum possible profit = 235
