डीएए - आंशिक नाक

लालची एल्गोरिथ्म को एक अच्छी तरह से ज्ञात समस्या के साथ अच्छी तरह से समझा जा सकता है जिसे नैकपैक समस्या कहा जाता है। यद्यपि अन्य एल्गोरिथम दृष्टिकोणों को नियोजित करके एक ही समस्या को हल किया जा सकता है, लेकिन लालची दृष्टिकोण एक अच्छे समय में आंशिक रूप से नैकपैक समस्या का हल करता है। आइए विस्तार से चर्चा करते हैं नैकपैक समस्या पर।

क्लेश समस्या

वस्तुओं के एक सेट को देखते हुए, प्रत्येक में एक वजन और एक मूल्य होता है, एक संग्रह में शामिल करने के लिए वस्तुओं का एक सबसेट निर्धारित करते हैं ताकि कुल वजन किसी निर्धारित सीमा से कम या बराबर हो और कुल मूल्य यथासंभव बड़ा हो।

कॉम्पेक्टोरियल ऑप्टिमाइज़ेशन प्रॉब्लम में नैकपैक की समस्या है। यह वास्तविक दुनिया की समस्याओं के कई और अधिक जटिल गणितीय मॉडल में एक उपप्रम के रूप में प्रकट होता है। कठिन समस्याओं के लिए एक सामान्य दृष्टिकोण सबसे अधिक प्रतिबंधात्मक बाधा की पहचान करना, दूसरों की उपेक्षा करना, एक समस्या को हल करना है, और किसी भी तरह से उपेक्षित बाधाओं को संतुष्ट करने के लिए समाधान को समायोजित करना है।

अनुप्रयोग

कुछ बाधाओं के साथ संसाधन आवंटन के कई मामलों में, समस्या को एक समान तरीके से Knapsack समस्या से निकाला जा सकता है। निम्नलिखित उदाहरण का एक सेट है।

कच्चे माल को काटने के लिए कम से कम बेकार रास्ता खोजना
पोर्टफोलियो अनुकूलन
शेयर समस्याओं में कटौती

समस्या परिदृश्य

एक चोर एक दुकान को लूट रहा है और अधिकतम वजन उठा सकता है Wउसकी नोकझोंक में। स्टोर और वजन में उपलब्ध एन आइटम हैंi^th आइटम है w_i और इसका लाभ है p_i। चोर को क्या सामान लेना चाहिए?

इस संदर्भ में, आइटम को इस तरह से चुना जाना चाहिए कि चोर उन वस्तुओं को ले जाएगा जिसके लिए वह अधिकतम लाभ प्राप्त करेगा। इसलिए, चोर का उद्देश्य लाभ को अधिकतम करना है।

वस्तुओं की प्रकृति के आधार पर, नॅप्सैक समस्याओं को वर्गीकृत किया गया है

आंशिक नाक
Knapsack

आंशिक नाक

इस मामले में, आइटम को छोटे टुकड़ों में तोड़ा जा सकता है, इसलिए चोर आइटम के अंशों का चयन कर सकता है।

समस्या कथन के अनुसार,

वहां n स्टोर में आइटम
का वजन i^th आइटम $ w_ {i}> 0 $
के लिए लाभ i^th आइटम $ p_ {i}> 0 $ और
नैकसैक की क्षमता है W

नॅप्सैक समस्या के इस संस्करण में, आइटमों को छोटे टुकड़ों में तोड़ा जा सकता है। तो, चोर केवल एक अंश ले सकता हैx_i का i^th आइटम।

$ $ 0 \ leqslant x_ {i} \ leqslant 1 $ $

i^th आइटम वजन में योगदान देता है $ x_ {i} .w_ {i} knapsack में कुल वजन में $ और लाभ $ x_ {i} .p_ {i} $ कुल लाभ के लिए।

इसलिए, इस एल्गोरिथ्म का उद्देश्य है

$ $ अधिकतम \: \ प्रदर्शन शैली \ योग \ सीमा_ {n = 1} ^ n (x_ {i} .p _ {} i) $ $।

बाधा के अधीन,

$$ \ displaystyle \ sum \ limit_ {n = 1} ^ n (x_ {i} .w _ {} i) \ leqslant W $$

यह स्पष्ट है कि एक इष्टतम समाधान को पूरी तरह से नैकपैक भरना चाहिए, अन्यथा हम शेष वस्तुओं में से एक का एक अंश जोड़ सकते हैं और समग्र लाभ बढ़ा सकते हैं।

इस प्रकार, एक इष्टतम समाधान द्वारा प्राप्त किया जा सकता है

$$ \ displaystyle \ sum \ limit_ {n = 1} ^ n (x_ {i} .w _ {} i) = W $$

इस संदर्भ में, पहले हमें $ \ frac {p_ {i}} {w_ {i}} $ के मूल्य के अनुसार उन वस्तुओं को क्रमबद्ध करने की आवश्यकता है, ताकि $ \ frac {p_ {i} +1} {w_ {i } +1} $ \ $ \ frac {p_ {i}} {w_ {i}} $। यहाँ,x वस्तुओं के अंश को संग्रहीत करने के लिए एक सरणी है।

Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W) 
for i = 1 to n 
   do x[i] = 0 
weight = 0 
for i = 1 to n 
   if weight + w[i] ≤ W then  
      x[i] = 1 
      weight = weight + w[i] 
   else 
      x[i] = (W - weight) / w[i] 
      weight = W 
      break 
return x

विश्लेषण

यदि प्रदान की गई वस्तुएं पहले से ही $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} के घटते क्रम में छांटी जाती हैं, तो व्हेलिलोप में एक समय लगता है O(n); इसलिए, सॉर्ट सहित कुल समय में हैO(n logn)।

उदाहरण

आइए हम इस बात पर विचार करें कि नॉकसैक की क्षमता W = 60 और प्रदान की गई वस्तुओं की सूची निम्न तालिका में दिखाई गई है -

मद	ए	ख	सी	घ
फायदा	280	100	120	120
वजन	40	10	20	24
अनुपात $ (\ frac {p_ {i}} {w_ {i}}) $	7	10	6	5

चूँकि प्रदान की गई वस्तुएँ $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $ के आधार पर सॉर्ट नहीं की जाती हैं। सॉर्ट करने के बाद, आइटम निम्न तालिका में दिखाए गए हैं।

मद	ख	ए	सी	घ
फायदा	100	280	120	120
वजन	10	40	20	24
अनुपात $ (\ frac {p_ {i}} {w_ {i}}) $	10	7	6	5

उपाय

$ \ Frac {p_ {i}} {w_ {i}} $ के अनुसार सभी वस्तुओं को छाँटने के बाद। सबसे पहलेB के वजन के रूप में चुना गया है Bकी क्षमता से कम है। अगला आइटमA चुना गया है, क्योंकि नैकपैक की उपलब्ध क्षमता वजन से अधिक है A। अभी,Cअगले आइटम के रूप में चुना गया है। हालाँकि, पूरे आइटम को नहीं चुना जा सकता है क्योंकि नैकपैक की शेष क्षमता वजन से कम हैC।

इसलिए, का अंश C (अर्थात (६० - ५०) / २०) चुना जाता है।

अब, Knapsack की क्षमता चयनित वस्तुओं के बराबर है। इसलिए, कोई और आइटम नहीं चुना जा सकता है।

चयनित वस्तुओं का कुल वजन है 10 + 40 + 20 * (10/20) = 60

और कुल लाभ है 100 + 280 + 120 * (10/20) = 380 + 60 = 440

यह इष्टतम समाधान है। हम वस्तुओं के किसी भी अलग संयोजन का चयन करके अधिक लाभ प्राप्त नहीं कर सकते हैं।