डीएए - 0-1 नैकपैक

इस ट्यूटोरियल में, पहले हमने लालची दृष्टिकोण का उपयोग करके फ्रैक्शनल नॅप्सैक समस्या पर चर्चा की है। हमने दिखाया है कि लालची दृष्टिकोण फ्रैक्शनल नॅपैक के लिए एक इष्टतम समाधान देता है। हालाँकि, यह अध्याय 0-1 नैकपैक समस्या और इसके विश्लेषण को कवर करेगा।

0-1 नैकपैक में, आइटम को तोड़ा नहीं जा सकता जिसका अर्थ है कि चोर को आइटम को एक पूरे के रूप में लेना चाहिए या इसे छोड़ देना चाहिए। इसे 0-1 नैकपैक के रूप में कहने के पीछे कारण है।

इसलिए, 0-1 नैकपैक के मामले में, का मूल्य x_i दोनोंमेसे एक हो सकता है 0 या 1, जहाँ अन्य बाधाएँ समान रहती हैं।

0-1 नैकपैक को लालची दृष्टिकोण से हल नहीं किया जा सकता है। लालची दृष्टिकोण एक इष्टतम समाधान सुनिश्चित नहीं करता है। कई उदाहरणों में, लालची दृष्टिकोण एक इष्टतम समाधान दे सकता है।

निम्नलिखित उदाहरण हमारे बयान को स्थापित करेंगे।

उदाहरण 1

आइए हम इस बात पर विचार करें कि नैकपैक की क्षमता W = 25 है और आइटम निम्न तालिका में दिखाए गए हैं।

मद	ए	बी	सी	डी
फायदा	24	18	18	10
वजन	24	10	10	7

प्रति यूनिट वजन पर लाभ पर विचार किए बिना (p_i/w_i), अगर हम इस समस्या को हल करने के लिए लालची दृष्टिकोण लागू करते हैं, तो पहले आइटम Aचुना जाएगा क्योंकि यह सभी तत्वों के बीच अधिकतम _i मम लाभ में योगदान देगा ।

आइटम का चयन करने के बाद A, और आइटम का चयन नहीं किया जाएगा। इसलिए, इस मद के लिए निर्धारित कुल लाभ है24। जबकि, आइटम का चयन करके इष्टतम समाधान प्राप्त किया जा सकता है,B और सी, जहां कुल लाभ 18 + 18 = 36 है।

उदाहरण -2

समग्र लाभ के आधार पर वस्तुओं का चयन करने के बजाय, इस उदाहरण में आइटमों का चयन अनुपात p _i / w _{i के} आधार पर किया जाता है । आइए हम विचार करें कि नैकस्पैक की क्षमता W = 60 है और आइटम निम्न तालिका में दिखाए गए हैं।

मद	ए	बी	सी
कीमत	100	280	120
वजन	10	40	20
अनुपात	10	7	6

लालची दृष्टिकोण का उपयोग करना, पहले आइटम Aचूना गया। फिर, अगले आइटमBचुना जाता है। इसलिए, कुल लाभ है100 + 280 = 380। हालाँकि, आइटम का चयन करके इस उदाहरण का इष्टतम समाधान प्राप्त किया जा सकता है,B तथा C, जहां कुल लाभ होता है 280 + 120 = 400।

इसलिए, यह निष्कर्ष निकाला जा सकता है कि लालची दृष्टिकोण एक इष्टतम समाधान नहीं दे सकता है।

0-1 नैकपैक को हल करने के लिए, डायनामिक प्रोग्रामिंग दृष्टिकोण की आवश्यकता होती है।

समस्या का विवरण

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

डायनेमिक-प्रोग्रामिंग दृष्टिकोण

चलो i एक इष्टतम समाधान में सबसे अधिक संख्या वाली वस्तु हो S के लिये Wडॉलर। फिरS^' = S - {i} के लिए एक इष्टतम समाधान है W - w_i डॉलर और समाधान के लिए मूल्य S है V_i प्लस उप समस्या का मूल्य।

हम इस तथ्य को निम्न सूत्र में व्यक्त कर सकते हैं: परिभाषित करें c[i, w] वस्तुओं के लिए समाधान होना 1,2, … , iऔर अधिकतम _आई मम वजनw।

एल्गोरिथ्म निम्नलिखित जानकारी लेता है

• अधिकतम _मैं मम वजनW

• मदों की संख्या n

• दो क्रम v = <v₁, v₂, …, v_n> तथा w = <w₁, w₂, …, w_n>

Dynamic-0-1-knapsack (v, w, n, W) 
for w = 0 to W do 
   c[0, w] = 0 
for i = 1 to n do 
   c[i, 0] = 0 
   for w = 1 to W do 
      if wi ≤ w then 
         if vi + c[i-1, w-wi] then 
            c[i, w] = vi + c[i-1, w-wi] 
         else c[i, w] = c[i-1, w] 
      else 
         c[i, w] = c[i-1, w]

शुरू करने के लिए आइटम के सेट को टेबल से घटाया जा सकता है c[n, w] और पीछे की ओर ट्रेसिंग जहां से इष्टतम मान आए।

यदि c [i, w] = c [i-1, w] , तो आइटमi समाधान का हिस्सा नहीं है, और हम साथ अनुरेखण जारी रखते हैं c[i-1, w]। अन्यथा, आइटमi समाधान का हिस्सा है, और हम साथ अनुरेखण जारी रखते हैं c[i-1, w-W]।

विश्लेषण

यह एल्गोरिथ्म (( n , w ) बार लेता है क्योंकि तालिका c में ( n + 1) है। ( w + 1) प्रविष्टियां, जहां प्रत्येक प्रविष्टि को गणना करने के लिए each (1) समय की आवश्यकता होती है।