भिन्नात्मक बस्ता समस्या: उदाहरण के साथ लालची एल्गोरिथ्म
लालची रणनीति क्या है?
लालची एल्गोरिदम गतिशील प्रोग्रामिंग एल्गोरिदम की तरह होते हैं जिनका उपयोग अक्सर इष्टतम समस्याओं को हल करने के लिए किया जाता है (किसी विशेष मानदंड के अनुसार समस्या का सर्वोत्तम समाधान ढूंढना)।
लालची एल्गोरिदम इष्टतम स्थानीय चयनों को इस उम्मीद में लागू करते हैं कि वे चयन समस्या के समाधान के लिए इष्टतम वैश्विक समाधान की ओर ले जाएंगे। लालची एल्गोरिदम अक्सर सेट अप करने में बहुत कठिन नहीं होते हैं, तेज़ होते हैं (समय जटिलता अक्सर एक रैखिक फ़ंक्शन या बहुत हद तक दूसरे क्रम का फ़ंक्शन होती है)। इसके अलावा, इन कार्यक्रमों को डीबग करना मुश्किल नहीं है और कम मेमोरी का उपयोग करते हैं। लेकिन परिणाम हमेशा एक इष्टतम समाधान नहीं होते हैं।
लालची रणनीतियों का उपयोग अक्सर एक विकल्प A बनाकर संयोजन अनुकूलन समस्या को हल करने के लिए किया जाता है। विकल्प A का निर्माण A के प्रत्येक घटक Ai को पूरा होने तक (पर्याप्त n घटक) चुनकर किया जाता है। प्रत्येक Ai के लिए, आप Ai को इष्टतम रूप से चुनते हैं। इस तरह, यह संभव है कि अंतिम चरण में आपके पास चुनने के लिए कुछ भी न हो, लेकिन अंतिम शेष मान को स्वीकार करना पड़े।
लालची निर्णयों के दो महत्वपूर्ण घटक हैं:
- लालची चयन का तरीका। आप चुन सकते हैं कि वर्तमान में कौन सा समाधान सबसे अच्छा है और फिर अंतिम चयन करने से उत्पन्न होने वाली उप-समस्या को हल करें। लालची एल्गोरिदम का चयन पिछले चयनों पर निर्भर हो सकता है। लेकिन यह किसी भी भविष्य के चयन या उप-समस्याओं के समाधान पर निर्भर नहीं हो सकता है। एल्गोरिदम इस तरह से विकसित होता है कि लूप में चयन करता है, साथ ही दी गई समस्या को छोटी उप-समस्याओं में छोटा कर देता है।
- इष्टतम उपसंरचना। आप किसी समस्या के लिए इष्टतम उपसंरचना का प्रदर्शन करते हैं यदि इस समस्या के इष्टतम समाधान में इसकी उपसमस्याओं के लिए इष्टतम समाधान शामिल हैं।
एक लालची एल्गोरिथ्म में पांच घटक होते हैं:
- उम्मीदवारों का एक समूह, जिसमें से समाधान तैयार किया जाना है।
- समाधान में जोड़ने के लिए सर्वोत्तम उम्मीदवार का चयन करने हेतु एक चयन फ़ंक्शन।
- एक व्यवहार्य फ़ंक्शन का उपयोग यह तय करने के लिए किया जाता है कि क्या किसी उम्मीदवार का उपयोग समाधान बनाने के लिए किया जा सकता है।
- एक उद्देश्य फ़ंक्शन, जो किसी समाधान या अपूर्ण समाधान का मान निर्धारित करता है।
- एक मूल्यांकन फ़ंक्शन, जो यह बताता है कि आपको पूर्ण समाधान कब मिला।
लालची व्यक्ति का विचार
पहले विचार के साथ, आपके पास लालची एक के निम्नलिखित चरण हैं:
- मानों को गैर-बढ़ते क्रम में क्रमबद्ध करें.
- आदेशित पैकेजों पर बारी-बारी से विचार करें, यदि बैग की शेष क्षमता उसे रखने के लिए पर्याप्त है तो बैग में विचाराधीन पैकेज को डालें (जिसका अर्थ है कि बैग में डाले गए पैकेजों का कुल वजन और विचाराधीन पैकेजों का वजन बैग की क्षमता से अधिक नहीं होना चाहिए)।
हालाँकि, यह लालची एल्गोरिथ्म हमेशा इष्टतम समाधान नहीं देता है। यहाँ आपके पास एक प्रति-उदाहरण है:
- समस्या के पैरामीटर हैं: n = 3; M = 19.
- पैकेज: {i = 1; W[i] = 14; V[i] = 20}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 8} -> बहुत बढ़िया मूल्य लेकिन साथ ही बहुत बड़ा वजन भी।
- एल्गोरिथ्म 1 के कुल मान के साथ पैकेज 20 का चयन करेगा, जबकि समस्या का इष्टतम समाधान 2 के कुल मान के साथ (पैकेज 3, पैकेज 24) चुना जाता है।
लालची दो का विचार
दूसरे विचार के साथ, आपके पास लालची दो के निम्नलिखित चरण हैं:
- भार को गैर-घटते क्रम में क्रमबद्ध करें।
- आदेशित पैकेजों पर बारी-बारी से विचार करें, यदि बैग की शेष क्षमता उसे रखने के लिए पर्याप्त है तो बैग में विचाराधीन पैकेज को डालें (जिसका अर्थ है कि बैग में डाले गए पैकेजों का कुल वजन और विचाराधीन पैकेजों का वजन बैग की क्षमता से अधिक नहीं होना चाहिए)।
हालाँकि, यह लालची एल्गोरिथ्म हमेशा इष्टतम समाधान नहीं देता है। यहाँ आपके पास एक प्रति-उदाहरण है:
- समस्या के पैरामीटर हैं: n = 3; M = 11.
- पैकेज: {i = 1; W[i] = 5; V[i] = 10}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 28} -> वजन हल्का है लेकिन कीमत भी बहुत कम है।
- एल्गोरिथ्म 1 के कुल मान के साथ (पैकेज 2, पैकेज 26) का चयन करेगा, जबकि समस्या का इष्टतम समाधान 3 के कुल मान के साथ (पैकेज 28) है।
लालची तीन का विचार
तीसरे विचार के साथ, आपके पास लालची तीन के निम्नलिखित चरण हैं। वास्तव में, यह सबसे व्यापक रूप से इस्तेमाल किया जाने वाला एल्गोरिदम है।
- पैकेजों को इकाई लागत के मूल्य में वृद्धि न होने के क्रम में क्रमबद्ध करें . आपके पास:
- आदेशित पैकेजों पर बारी-बारी से विचार करें, यदि बैग की शेष क्षमता उसे रखने के लिए पर्याप्त है तो बैग में विचाराधीन पैकेज को डालें (जिसका अर्थ है कि बैग में डाले गए पैकेजों का कुल वजन और विचाराधीन पैकेजों का वजन बैग की क्षमता से अधिक नहीं होना चाहिए)।
विचारउस समस्या का लालची विचार गणना करना है प्रत्येक का अनुपात . फिर इन अनुपातों को अवरोही क्रम में छाँटें। आप सबसे ज़्यादा वाला चुनेंगे पैकेज और बस्ते की क्षमता उस पैकेज को समाहित कर सकती है (शेष > wi) हर बार जब कोई सामान बस्ते में डाला जाता है, तो इससे बस्ते की क्षमता भी कम हो जाती है।
पैकेज चुनने का तरीका:
- इकाई लागतों की सरणी पर विचार करें। आप घटती इकाई लागतों के अनुसार पैकेजों का चयन करते हैं।
- मान लीजिए आपको आंशिक समाधान मिल गया: (x1, …, एक्सi).
- बस्ते का मूल्य प्राप्त किया जाता है:
- बस्ते में रखे गए पैकेटों के वजन के अनुसार:
- इसलिए, बस्ते की शेष वजन सीमा है:
एल्गोरिथ्म के चरण
आप देख सकते हैं कि यह अधिकतम खोजने की समस्या है। पैकेजों की सूची को शाखाकरण पर विचार करने के लिए इकाई लागत के अवरोही क्रम में क्रमबद्ध किया गया है।
- चरण 1नोड रूट नैपसेक की प्रारंभिक स्थिति को दर्शाता है, जहां आपने कोई पैकेज नहीं चुना है।
- कुल मान = 0.
- मूल नोड की ऊपरी सीमा UpperBound = M * अधिकतम इकाई लागत.
- चरण 2: नोड रूट में सबसे बड़ी यूनिट लागत वाले पैकेज को चुनने की क्षमता के अनुरूप चाइल्ड नोड होंगे। प्रत्येक नोड के लिए, आप पैरामीटर की पुनः गणना करते हैं:
- कुल मूल्य = कुल मूल्य (पुराना) + चयनित पैकेजों की संख्या * प्रत्येक पैकेज का मूल्य।
- M = M (पुराना) - चयनित पैकेजों की संख्या * प्रत्येक पैकेज का वजन।
- अपरबाउंड = कुल मूल्य + एम (नया) * अगले विचार किए जाने वाले पैकेज की इकाई लागत।
- चरण 3: चाइल्ड नोड्स में, आप बड़ी ऊपरी सीमा वाले नोड के लिए ब्रांचिंग को प्राथमिकता देंगे। इस नोड के बच्चे बड़ी यूनिट लागत वाले अगले पैकेज को चुनने की क्षमता के अनुरूप हैं। प्रत्येक नोड के लिए, आपको चरण 2 में उल्लिखित सूत्र के अनुसार TotalValue, M, UpperBound मापदंडों की फिर से गणना करनी होगी।
- चरण 4: चरण 3 को इस नोट के साथ दोहराएँ: जिन नोड्स की ऊपरी सीमा, किसी विकल्प की अस्थायी अधिकतम लागत से कम या बराबर है, उनके लिए आपको अब उस नोड के लिए शाखा बनाने की आवश्यकता नहीं है।
- चरण 5यदि सभी नोड्स शाखाबद्ध या कटे हुए हैं, तो सबसे महंगा विकल्प ही तलाशना चाहिए।
एल्गोरिथ्म के लिए छद्म कोड:
Fractional Knapsack (Array W, Array V, int M) 1. for i <- 1 to size (V) 2. calculate cost[i] <- V[i] / W[i] 3. Sort-Descending (cost) 4. i ← 1 5. while (i <= size(V)) 6. if W[i] <= M 7. M ← M – W[i] 8. total ← total + V[i]; 9. if W[i] > M 10. i ← i+1
एल्गोरिथ्म की जटिलता:
- यदि सरल सॉर्ट एल्गोरिथ्म (चयन, बबल...) का उपयोग किया जाए तो पूरी समस्या की जटिलता O(n2) है।
- यदि त्वरित सॉर्ट या मर्ज सॉर्ट का उपयोग किया जाए तो पूरी समस्या की जटिलता O(nlogn) होगी।
Java लालची तीन के लिए कोड
- सबसे पहले, आप क्लास KnapsackPackage को परिभाषित करते हैं। इस क्लास में गुण हैं: वजन, मूल्य और प्रत्येक पैकेज की संगत लागत। इस क्लास की संपत्ति लागत का उपयोग मुख्य एल्गोरिथ्म में सॉर्टिंग कार्य के लिए किया जाता है। प्रत्येक लागत का मूल्य है प्रत्येक पैकेज का अनुपात.
public class KnapsackPackage { private double weight; private double value; private Double cost; public KnapsackPackage(double weight, double value) { super(); this.weight = weight; this.value = value; this.cost = new Double(value / weight); } public double getWeight() { return weight; } public double getValue() { return value; } public Double getCost() { return cost; } }
- फिर आप एल्गोरिथ्म लालची तीन को निष्पादित करने के लिए एक फ़ंक्शन बनाते हैं।
public void knapsackGreProc(int W[], int V[], int M, int n) { KnapsackPackage[] packs = new KnapsackPackage[n]; for (int i = 0; i < n; i ++) { packs[i] = new KnapsackPackage(W[i], V[i]); } Arrays.sort(packs, new Comparator<KnapsackPackage>() { @Override public int compare(KnapsackPackage kPackA, KnapsackPackage kPackB) { return kPackB.getCost().compareTo(kPackA.getCost()); } }); int remain = M; double result = 0d; int i = 0; boolean stopProc = false; while (!stopProc) { if (packs[i].getWeight() <= remain) { remain -= packs[i].getWeight(); result += packs[i].getValue(); System.out.println("Pack " + i + " - Weight " + packs[i].getWeight() + " - Value " + packs[i].getValue()); } if (packs[i].getWeight() > remain) { i ++; } if (i == n) { stopProc = true; } } System.out.println("Max Value:\t" + result); }
कोड का स्पष्टीकरण:
- प्रत्येक नैपसेक पैकेज के लिए वजन और मूल्य आरंभ करें।
- बैग के पैकेजों को लागत के अनुसार अवरोही क्रम में छाँटें।
- यदि पैकेज का चयन करें i.
- यदि पैकेज की संख्या का चयन करें तो यह पर्याप्त है।
- सभी पैकेज ब्राउज़ करते समय रुकें.
इस ट्यूटोरियल में, आपके पास दो उदाहरण हैं। यहाँ दो उदाहरणों के साथ उपरोक्त प्रोग्राम को चलाने के लिए जावा कोड दिया गया है:
public void run() { /* * Pack and Weight - Value */ //int W[] = new int[]{15, 10, 2, 4}; int W[] = new int[]{12, 2, 1, 1, 4}; //int V[] = new int[]{30, 25, 2, 6}; int V[] = new int[]{4, 2, 1, 2, 10}; /* * Max Weight */ //int M = 37; int M = 15; int n = V.length; /* * Run the algorithm */ knapsackGreProc(W, V, M, n); }
आपके पास आउटपुट है:
- पहला उदाहरण:
Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 2 - Weight 4.0 - Value 6.0 Pack 3 - Weight 2.0 - Value 2.0 Max Value: 83.0
- दूसरा उदाहरण:
Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Max Value: 36.0
पहले उदाहरण का विश्लेषण करें:
- समस्या के पैरामीटर हैं: n = 4; M = 37.
- पैकेज: {i = 1; W[i] = 15; V[i] = 30; लागत = 2.0}; {i = 2; W[i] = 10; V[i] = 25; लागत = 2.5}; {i = 3; W[i] = 2; V[i] = 4; लागत = 1.0}; {i = 4; W[i] = 4; V[i] = 6; लागत = 1.5}.
- आप पैकेजों को इकाई लागत के मूल्य में कोई वृद्धि न करने के क्रम में क्रमबद्ध करते हैं। आपके पास है: {i = 2} -> {i = १} -> {i = १} -> {i = 3}.
पहले उदाहरण के लिए एल्गोरिथ्म लागू करने के चरण:
- x1, x2, x3, x4 को प्रत्येक चयनित पैकेज की संख्या के रूप में परिभाषित करें, जो पैकेज {i = 2} के अनुरूप है -> {i = १} -> {i = १} -> {i = 3}.
- नोड रूट N उस स्थिति को दर्शाता है जिसमें आपने कोई पैकेज नहीं चुना है। फिर:
- कुल मान = 0.
- एम = 37 (जैसा प्रस्तावित है).
- अपरबाउंड = 37 * 2.5 = 92.5, जिसमें से 37 M है और 2.5 पैकेज की इकाई लागत है {i = 2}।
- पैकेज {i = 2} के साथ, आपके पास 4 संभावनाएँ हैं: 3 पैकेज {i = 2} (x1 = 3) चुनें; 2 पैकेज {i = 2} (x1 = 2) चुनें; 1 पैकेज {i = 2} (x1 = 1) चुनें और पैकेज {i = 2} (x1 = 0) न चुनें। इन 4 संभावनाओं के अनुसार, आप रूट नोड N को 4 बच्चों N[1], N[2], N[3] और N[4] में विभाजित करते हैं।
- चाइल्ड नोड N1 के लिए, आपके पास है:
- कुल मान = 0 + 3 * 25 = 75, जहाँ 3 चयनित पैकेज {i = 2} की संख्या है और 25 प्रत्येक पैकेज का मान है {i = 2}.
- M = 37 – 3 * 10 = 7, जहाँ 37 बस्ते की प्रारंभिक मात्रा है, 3 पैकेज की संख्या है {i = 2}, 10 प्रत्येक पैकेज का वजन है {i = 2}।
- अपरबाउंड = 75 + 7 * 2 = 89, जहां 75 कुल मूल्य है, 7 बस्ते का शेष वजन है और 2 पैकेज की इकाई लागत है {i = 1}।
- इसी तरह, आप नोड्स N[2], N[3] और N[4] के लिए मापदंडों की गणना कर सकते हैं, जिसमें अपरबाउंड क्रमशः 84, 79 और 74 है।
- नोड्स N[1], N[2], N[3] और N[4] में से, नोड N[1] का अपरबाउंड सबसे बड़ा है, इसलिए आप नोड N[1] को पहले ब्रांच करेंगे इस उम्मीद में कि इस दिशा से एक अच्छी योजना होगी।
- नोड N[1] से, आपके पास x1 = 1 के अनुरूप केवल एक चाइल्ड नोड N[2-0] है (बैकपैक का शेष वजन 7 है, जबकि प्रत्येक पैकेज {i = 1} का वजन 15 है)। N[1-1] बटन के लिए पैरामीटर निर्धारित करने के बाद आपके पास N[1-1] का अपरबाउंड 85.5 है।
- आप नोड N[1-1] की शाखा बनाना जारी रखते हैं। नोड N[1-1] के 2 बच्चे N[1-1-1] और N[1-1-2] हैं जो x3 = 1 और x3 = 0 के अनुरूप हैं। इन दो नोड्स के लिए पैरामीटर निर्धारित करने के बाद, आप देखते हैं कि N[1-1-1] की ऊपरी सीमा 84 है और N[1-1-2] की 82 है, इसलिए आप नोड N[1-1-1] की शाखा बनाना जारी रखते हैं।
- नोड N[1-1-1] में दो संतानें हैं, N[1-1-1-1] और N[1-1-1-2], जो x4 = 1 और x4 = 0 के अनुरूप हैं। ये दो लीफ नोड हैं (विकल्प का प्रतिनिधित्व करते हैं) क्योंकि प्रत्येक नोड के लिए पैकेजों की संख्या चुनी गई है। जिसमें नोड N[1-1-1-1] 1 के लिए विकल्प x3 = 2, x0 = 3, x1 = 4 और x1 = 83 का प्रतिनिधित्व करता है, जबकि नोड N[1-1-1-2] 1 पर विकल्प x3 = 2, x0 = 3, x1 = 4 और x01 = 81 का प्रतिनिधित्व करता है। इसलिए यहाँ अस्थायी अधिकतम मान 83 है।
- नोड N[1-1-2] पर वापस मुड़ते हुए, आप देखते हैं कि N[1-1-2] का अपरबाउंड 82 < 83 है, इसलिए आप नोड N[1-1-2] को ट्रिम करते हैं।
- नोड N2 पर वापस आते हुए, आप देखते हैं कि N2 का अपरबाउंड 84 > 83 है, इसलिए आप नोड N2 को ब्रांच करना जारी रखते हैं। नोड N2 के दो बच्चे N[2-1] और N[2-2] हैं जो x2 = 1 और x2 = 0 के अनुरूप हैं। N[2-1] और N[2-2] के लिए मापदंडों की गणना करने के बाद, आप देखते हैं कि N[2-1] का अपरबाउंड 83 है और N[2-2] का 75.25 है। इनमें से कोई भी मान 83 से अधिक नहीं है, इसलिए दोनों नोड्स को ट्रिम किया जाता है।
- अंत में, नोड्स N3 और N4 को भी ट्रिम किया जाता है।
- इसलिए पेड़ पर सभी नोड्स को शाखाबद्ध या छंटनी की जाती है, इसलिए सबसे अच्छा अस्थायी समाधान वह है जिसे तलाशना है। तदनुसार, आपको 3 पैकेज {i = 2}, 1 पैकेज {i = 4} और एक पैकेज {i = 3} का चयन करना होगा, जिसका कुल मूल्य 83 है, कुल वजन 36 है।
दूसरे उदाहरण के समान विश्लेषण से आपको परिणाम मिलता है: पैकेज 4 (3 बार) और पैकेज 5 (3 बार) का चयन करें।
Pythonलालची तीन के लिए 3 कोड
- सबसे पहले, आप KnapsackPackage वर्ग को परिभाषित करें।
class KnapsackPackage(object): """ Knapsack Package Data Class """ def __init__(self, weight, value): self.weight = weight self.value = value self.cost = value / weight def __lt__(self, other): return self.cost < other.cost
- फिर आप एल्गोरिथ्म लालची तीन को निष्पादित करने के लिए एक फ़ंक्शन बनाते हैं।
class FractionalKnapsack(object): def __init__(self): def knapsackGreProc(self, W, V, M, n): packs = [] for i in range(n): packs.append(KnapsackPackage(W[i], V[i])) packs.sort(reverse = True) remain = M result = 0 i = 0 stopProc = False while (stopProc != True): if (packs[i].weight <= remain): remain -= packs[i].weight; result += packs[i].value; print("Pack ", i, " - Weight ", packs[i].weight, " - Value ", packs[i].value) if (packs[i].weight > remain): i += 1 if (i == n): stopProc = True print("Max Value:\t", result)
कोड का स्पष्टीकरण:
- प्रत्येक नैपसेक पैकेज के लिए वजन और मूल्य आरंभ करें।
- बैग के पैकेजों को लागत के अनुसार अवरोही क्रम में छाँटें।
- यदि पैकेज का चयन करें i.
- यदि पैकेज की संख्या का चयन करें तो यह पर्याप्त है।
- सभी पैकेज ब्राउज़ करते समय रुकें.
यहाँ है Pythonपहले उदाहरण के साथ उपरोक्त प्रोग्राम को चलाने के लिए कोड 3:
if __name__ == "__main__": W = [15, 10, 2, 4] V = [30, 25, 2, 6] M = 37 n = 4 proc = FractionalKnapsack() proc.knapsackGreProc(W, V, M, n)
आपके पास आउटपुट है:
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
लालची तीन के लिए C# कोड
- सबसे पहले, आप KnapsackPackage वर्ग को परिभाषित करें।
using System; namespace KnapsackProblem { public class KnapsackPackage { private double weight; private double value; private double cost; public KnapsackPackage(double weight, double value) { this.weight = weight; this.value = value; this.cost = (double) value / weight; } public double Weight { get { return weight; } } public double Value { get { return value; } } public double Cost { get { return cost; } } } }
- फिर आप एल्गोरिथ्म लालची तीन को निष्पादित करने के लिए एक फ़ंक्शन बनाते हैं।
using System; namespace KnapsackProblem { public class FractionalKnapsack { public FractionalKnapsack() { } public void KnapsackGreProc(int[] W, int[] V, int M, int n) { KnapsackPackage[] packs = new KnapsackPackage[n]; for (int k = 0; k < n; k++) packs[k] = new KnapsackPackage(W[k], V[k]); Array.Sort<KnapsackPackage>(packs, new Comparison<KnapsackPackage>( (kPackA, kPackB) => kPackB.Cost.CompareTo(kPackA.Cost))); double remain = M; double result = 0d; int i = 0; bool stopProc = false; while (!stopProc) { if (packs[i].Weight <= remain) { remain -= packs[i].Weight; result += packs[i].Value; Console.WriteLine("Pack " + i + " - Weight " + packs[i].Weight + " - Value " + packs[i].Value); } if (packs[i].Weight > remain) { i++; } if (i == n) { stopProc = true; } } Console.WriteLine("Max Value:\t" + result); } } }
कोड का स्पष्टीकरण:
- प्रत्येक नैपसेक पैकेज के लिए वजन और मूल्य आरंभ करें।
- बैग के पैकेजों को लागत के अनुसार अवरोही क्रम में छाँटें।
- यदि पैकेज का चयन करें i.
- यदि पैकेज की संख्या का चयन करें तो यह पर्याप्त है।
- सभी पैकेज ब्राउज़ करते समय रुकें.
पहले उदाहरण के साथ उपरोक्त प्रोग्राम को चलाने के लिए C# कोड यहां दिया गया है:
public void run() { /* * Pack and Weight - Value */ int[] W = new int[]{15, 10, 2, 4}; //int[] W = new int[] { 12, 2, 1, 1, 4 }; int[] V = new int[]{30, 25, 2, 6}; //int[] V = new int[] { 4, 2, 1, 2, 10 }; /* * Max Weight */ int M = 37; //int M = 15; int n = V.Length; /* * Run the algorithm */ KnapsackGreProc(W, V, M, n); }
आपके पास आउटपुट है:
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
लालची तीन का प्रति-उदाहरण
लालची तीन का एल्गोरिथ्म जल्दी से हल हो जाता है और कुछ मामलों में इष्टतम भी हो सकता है। हालाँकि, कुछ विशेष मामलों में, यह इष्टतम समाधान नहीं देता है। यहाँ आपके पास एक प्रति-उदाहरण है:
- समस्या के पैरामीटर हैं: n = 3; M = 10.
- पैकेज: {i = 1; W[i] = 7; V[i] = 9; लागत = 9/7}; {i = 2; W[i] = 6; V[i] = 6; लागत = 1}; {i = 3; W[i] = 4; V[i] = 4; लागत = 1}.
- एल्गोरिथ्म 1 के कुल मान के साथ (पैकेज 9) का चयन करेगा, जबकि समस्या का इष्टतम समाधान 2 के कुल मान के साथ (पैकेज 3, पैकेज 10) है।
उपरोक्त प्रोग्राम को प्रति-उदाहरण के साथ चलाने के लिए जावा कोड यहां दिया गया है:
public void run() { /* * Pack and Weight - Value */ int W[] = new int[]{7, 6, 4}; int V[] = new int[]{9, 6, 4}; /* * Max Weight */ int M = 10; int n = V.length; /* * Run the algorithm */ knapsackGreProc(W, V, M, n); }
यहाँ परिणाम है:
Pack 0 - Weight 7.0 - Value 9.0 Max Value: 9.0
फ्रैक्शनल नैप्सैक समस्या का यही सब कुछ है।