विचार इस तथ्य को लागू करने का है कि लालची दृष्टिकोण भिन्नात्मक बस्ता समस्या का सबसे अच्छा समाधान प्रदान करता है।
यह जांचने के लिए कि कोई विशेष नोड हमें बेहतर समाधान दे सकता है या नहीं, हम लालची दृष्टिकोण को लागू करने वाले इष्टतम समाधान (नोड के माध्यम से) की गणना करते हैं। यदि लालची दृष्टिकोण द्वारा परिकलित समाधान स्वयं अब तक के सर्वोत्तम समाधान से अधिक है, तो हम नोड के माध्यम से बेहतर समाधान प्राप्त नहीं कर सकते हैं।
पूरा एल्गोरिथम नीचे दिया गया है -
-
मूल्य प्रति यूनिट वजन के अनुपात के घटते क्रम के अनुसार सभी वस्तुओं को क्रमबद्ध करें ताकि एक ऊपरी सीमा की गणना लालची दृष्टिकोण को लागू करने के लिए की जा सके।
-
अधिकतम लाभ शुरू करें, जैसे कि maxProfit =0
-
एक खाली कतार, Q, बनाई जाती है।
-
डिसीजन ट्री का एक डमी नोड बनाया जाता है और इसे Q. में सम्मिलित या एनक्यू किया जाता है। डमी नोड का लाभ और वजन 0.
-
Q के खाली या खाली न होने पर निम्नलिखित करें।
-
Q से एक आइटम बनाया जाता है। निकाले गए आइटम को यू होने दें।
-
अगले स्तर के नोड के लाभ की गणना करें। यदि लाभ maxProfit से अधिक है, तो maxProfit को संशोधित करें।
-
अगले स्तर के नोड की बाध्यता की गणना करें। यदि बाउंड मैक्सप्रॉफिट से अधिक है, तो अगले स्तर के नोड को Q में जोड़ें।
-
उस मामले पर विचार करें जब अगले स्तर के नोड का इलाज नहीं किया जाता है या समाधान के हिस्से के रूप में नहीं माना जाता है और अगले स्तर के नोड के साथ कतार में एक नोड जोड़ें, लेकिन अगले स्तर के नोड्स का इलाज या विचार किए बिना वजन और लाभ।
-
नीचे दिए गए चित्र -
इनपुट
// First thing in every pair is treated as weight of item
// and second thing is treated as value of item
Item arr1[] = {{2, 40}, {3.14, 50}, {1.98, 100}, {5, 95}, {3, 30}};
Knapsack Capacity W1 = 10
आउटपुट
The maximum possible profit = 235