dynamic-programming
क्लेश समस्या

टिप्पणियों

0-1 नैकपैक समस्या

मान लीजिए कि आपसे पूछा गया है, कुल वजन जिसे आप अपने बस्ता और कुछ वस्तुओं के साथ अपने वजन और मूल्यों पर ले जा सकते हैं, तो आप उन वस्तुओं को इस तरह से कैसे ले सकते हैं कि उनके मूल्यों का योग अधिकतम हो, लेकिन उनके वजन का योग डॉन आप ले जा सकते हैं कुल वजन से अधिक नहीं? 0-1 इंगित करता है कि या तो आप आइटम चुनते हैं या आप नहीं करते हैं। इसके अलावा, हम प्रत्येक आइटम की एक मात्रा है। इसका मतलब है कि, आप आइटम को विभाजित नहीं कर सकते। यदि यह 0-1 नॅप्सैक समस्या नहीं थी, तो इसका मतलब है कि यदि आप वस्तुओं को विभाजित कर सकते हैं, तो इसके लिए एक लालची समाधान है, जिसे फ्रैक्शनल नॅप्सैक समस्या कहा जाता है ।

आइए, अब, हमारी समस्या पर ध्यान केंद्रित करें। उदाहरण के लिए, मान लें कि हमारे पास 7 की क्षमता है। हमारे पास 4 आइटम हैं। उनके वजन और मूल्य हैं:

+----------+---+---+---+---+
|   Item   | 1 | 2 | 3 | 4 |
+----------+---+---+---+---+
|  Weight  | 1 | 3 | 4 | 5 |
+----------+---+---+---+---+
|   Value  | 1 | 4 | 5 | 7 |
+----------+---+---+---+---+

एक क्रूर बल विधि सभी संभव संयोजनों को ले जा रही है। फिर हम उनके कुल वजन की गणना कर सकते हैं और उन्हें बाहर कर सकते हैं जो हमारे नैकपैक की क्षमता से अधिक है और वह पता लगाता है जो हमें अधिकतम मूल्य देता है। 4 वस्तुओं के लिए, हमें ( 4! - 1 ) = 23 संभावित संयोजनों की जाँच करने की आवश्यकता होगी (एक आइटम को छोड़कर)। वस्तुओं की संख्या बढ़ने पर यह काफी बोझिल हो जाता है। यहां, कुछ पहलुओं को हम देख सकते हैं, जो है:

• हम कम आइटम ले सकते हैं और उन वस्तुओं का उपयोग करके प्राप्त होने वाले अधिकतम मूल्य की गणना कर सकते हैं और उन्हें जोड़ सकते हैं। तो हमारी समस्या को उपप्रकारों में विभाजित किया जा सकता है।
• यदि हम आइटम {1,2} के लिए संयोजनों की गणना करते हैं, तो हम {1, 2, 3} की गणना करते समय इसका उपयोग कर सकते हैं।
• यदि हम वजन कम करते हैं और मूल्य को अधिकतम करते हैं, तो हम अपने इष्टतम समाधान का पता लगा सकते हैं।

इन कारणों से, हम अपनी समस्या को हल करने के लिए गतिशील प्रोग्रामिंग का उपयोग करेंगे। हमारी रणनीति यह होगी: जब भी कोई नया आइटम आता है, तो हम जाँच करेंगे कि क्या हम आइटम को चुन सकते हैं या नहीं और फिर हम उन वस्तुओं को चुनेंगे जो हमें अधिकतम मूल्य देती हैं। अब यदि हम आइटम को चुनते हैं, तो हमारा मूल्य आइटम का मूल्य होगा, और जो भी मूल्य हम अपनी क्षमता से मूल्य घटाकर प्राप्त कर सकते हैं और उस शेष वजन के लिए अधिकतम प्राप्त कर सकते हैं। यदि हम आइटम नहीं चुनते हैं, तो हम उन आइटमों को चुनेंगे जो हमें आइटम के बिना अधिकतम मूल्य देते हैं। आइए इसे हमारे उदाहरण से समझने की कोशिश करें:

हम एक 2D सरणी तालिका लेंगे, जहाँ आइटमों को ले कर हम अधिकतम कॉलम मान प्राप्त कर सकते हैं। 1. और पंक्तियों की संख्या वस्तुओं की संख्या के समान होगी। हमारे सरणी की तरह दिखेगा:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

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

हमारा पहला कॉलम 0 से भरा है। इसका मतलब है कि अगर हमारी अधिकतम क्षमता 0 है , तो कोई भी चीज हमारे पास नहीं है, क्योंकि हम किसी भी आइटम को नहीं चुन सकते हैं, हमारा अधिकतम मूल्य 0 होगा। तालिका [0] [1] से शुरू करते हैं। जब हम तालिका [1] [1] को भर रहे हैं, तो हम स्वयं से पूछ रहे हैं कि क्या हमारी अधिकतम क्षमता १ थी और हमारे पास केवल पहली वस्तु थी, हमारा अधिकतम मूल्य क्या होगा? आइटम उठाकर हम सबसे अच्छा 1 कर सकते हैं। तालिका [0] [2] के लिए इसका मतलब है कि अगर हमारी अधिकतम क्षमता 2 है और हमारे पास केवल पहला आइटम है, तो हम जो अधिकतम मूल्य प्राप्त कर सकते हैं वह 1 है । यह टेबल [0] [3] , टेबल [0] [4] , टेबल [0] [5] , टेबल [0] [6] और टेबल [0] [7] के लिए समान होगा । ऐसा इसलिए है क्योंकि हमारे पास केवल एक आइटम है, जो हमें 1 मूल्य देता है। चूँकि हमारे पास प्रत्येक आइटम की केवल 1 मात्रा है, चाहे हम किसी भी वस्तु से अपनी नोक-झोंक की क्षमता में वृद्धि क्यों न करें, 1 वह सर्वोत्तम मूल्य है जिसे हम बना सकते हैं। तो हमारे सरणी की तरह दिखेगा:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

आगे बढ़ते, टेबल के लिए [1] [1], हम अपने आप को, पूछ रहे हैं कि हम आइटम 1 और 2 था और अगर हमारे नैपसैक की अधिकतम क्षमता 1 था, अधिकतम मूल्य हम प्राप्त कर सकते हैं क्या है? यदि हम आइटम 1 और 2 दोनों लेते हैं, तो कुल वजन 4 होगा, जो हमारी वर्तमान नैकपैक क्षमता से अधिक होगा। इसलिए आइटम 2 का चयन नहीं किया जा सकता है। अब आइटम 2 न लेकर हम सबसे अच्छा क्या कर सकते हैं? शीर्ष से मान, वह तालिका [0] [1] है जिसमें अधिकतम मूल्य है जिसे हम प्राप्त कर सकते हैं यदि हमारे पास अधिकतम क्षमता 1 थी और हमने दूसरा आइटम नहीं चुना। टेबल के लिए [१] [२] , क्योंकि २ वज़न से कम है [२] , दूसरे आइटम का वजन है, हम आइटम नहीं ले सकते। इसलिए हम स्थापित कर सकते हैं, यदि वर्तमान वस्तु का वजन हमारी अधिकतम क्षमता से अधिक है, तो हम उस वस्तु को नहीं ले सकते। इस स्थिति में, हम बस ऊपर से मान लेंगे, जो कि आइटम को छोड़कर अधिकतम मूल्य का प्रतिनिधित्व करता है।

if weight[i] > j
    Table[i][j] := Table[i-1][j]
end if

अब टेबल के लिए [1] [३] चूंकि हमारी अधिकतम क्षमता हमारे वर्तमान वजन के बराबर है, इसलिए हमारे पास दो विकल्प हैं।

• हम आइटम को चुनते हैं और इस आइटम को लेने के बाद अन्य शेष वस्तुओं से प्राप्त अधिकतम मूल्य के साथ इसके मूल्य को जोड़ सकते हैं।
• हम इस आइटम को बाहर कर सकते हैं।

दो विकल्पों में से, हम वह चुनेंगे जिसमें से हम अधिकतम मूल्य प्राप्त कर सकते हैं। यदि हम आइटम का चयन करते हैं, तो हम प्राप्त करते हैं: इस आइटम के लिए मूल्य + इस आइटम को लेने के बाद बाकी वस्तुओं से अधिकतम मूल्य = 4 + 0 = 4 । हमें अपने वेट एरे से 4 (आइटम का मूल्य) मिलता है और 0 (इस आइटम को लेने के बाद हम बाकी चीजों से प्राप्त कर सकते हैं) 1 कदम ऊपर और 3 कदम पीछे जाकर मिलता है। वह सारणी [0] [0] है । क्यों? यदि हम आइटम लेते हैं, तो हमारी शेष क्षमता 3 - 3 = 0 होगी और शेष आइटम पहला आइटम होगा। यदि आप तालिका [0] को याद करते हैं तो ठीक है, [०] अगर हमारी क्षमता ० थी तो हम अधिकतम मूल्य जमा कर सकते हैं और हमारे पास केवल पहली वस्तु थी। अब यदि हम आइटम का चयन नहीं करते हैं, तो हम जो अधिकतम मूल्य प्राप्त कर सकते हैं, वह 1 कदम ऊपर से आता है, अर्थात 1 । अब हम इन दो मूल्यों ( 4 , 1 ) का अधिकतम लेते हैं और तालिका [1] [2] = 4 सेट करते हैं । तालिका [1] [४] के लिए , ४ के बाद से, अधिकतम अंतराल क्षमता ३ से अधिक है, हमारे वर्तमान आइटम का वजन, हमारे पास फिर से दो विकल्प हैं। हम अधिकतम ( वजन [2] + तालिका [0] [4-वजन [2]] , तालिका [0] [4] ) = अधिकतम ( वजन [2] + तालिका [0] [1] , तालिका [0] [४] ) = अधिकतम ( ४ + १ , १ ) = ५ ।

if weight[i] <= j
    w := weight[i]
    Table[i][j] := max(w + Table[i][j-w], Table[i-1][j])
end if

इन दो सूत्रों का उपयोग करके, हम पूरे सारणी सरणी को आबाद कर सकते हैं। हमारे सरणी की तरह दिखेगा:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 | 1 | 1 | 4 | 5 | 5 | 5 | 5 |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 | 1 | 1 | 4 | 5 | 6 | 6 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 | 1 | 1 | 4 | 5 | 7 | 8 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+

यहां, अंतिम मान जिसे हमने अपने एरे में डाला है, टेबल [3] [7] में हमारा आवश्यक अधिकतम मूल्य है। यह अधिकतम मूल्य है जिसे हम प्राप्त कर सकते हैं यदि हमारे पास 4 वस्तुएं थीं और हमारी नैकपैक की अधिकतम क्षमता 7 थी ।

यहां एक बात हमें याद रखनी चाहिए कि पहली पंक्ति के लिए भी, वज़न नापने की क्षमता से अधिक हो सकता है। हमें पहली पंक्ति को भरते समय मूल्य की जांच करने के लिए एक और बाधा रखने की आवश्यकता होगी। या हम केवल दूसरी पंक्ति ले सकते हैं और पहली पंक्ति के सभी मानों को 0 पर सेट कर सकते हैं। छद्म कोड की तरह दिखेगा:

Procedure Knapsack(Weight, Value, maxCapacity):
n := Item.size - 1
Table[n+1][maxCapacity+1]
for i from 0 to n
    Table[i][0] := 0
end for
for j from 1 to maxCapacity
    if j >= Weight[0]
        Table[0][j] := Weight[0]
    else
        Table[0][j] := 0
    end if
end for
for i from 1 to n
    for j from 1 to maxCapacity
        if Weight[i] >= j                                            //can't pick the item
            Table[i][j] := Table[i-1][j]        
        else                                                        //can pick the item
            w := Weight[i]
            Table[i][j] := max(w + Table[i-1][j-w], Table[i-1][j])
        end if
    end for
end for
Return Table[n][maxCapacity]

इस एल्गोरिथ्म के समय जटिलता है O(n*maxCapacity) , जहां n आइटम्स की संख्या है और maxCapacity हमारे नैपसैक की अधिकतम क्षमता है।

अब तक, हमने अपने उदाहरण से अधिकतम मूल्य प्राप्त किया है। एक सवाल अभी भी बना हुआ है। वास्तविक वस्तुएं क्या हैं? हम अपने टेबल एरे में मानों को वापस लेंगे, जो हमारे द्वारा लिए गए आइटमों का पता लगाने के लिए। हम दो रणनीतियों का पालन करेंगे:

• किसी भी आइटम के लिए, यदि मूल्य ऊपर की स्थिति से आ रहा है, तो हमने वर्तमान आइटम नहीं लिया। हम 1 कदम ऊपर जाते हैं।
• यदि मान ऊपर की स्थिति से नहीं आ रहा है, तो हमने आइटम लिया। तो हम 1 कदम ऊपर जाते हैं और x कदम पीछे जाते हैं जहां x वर्तमान वस्तु का वजन है।

छद्म कोड होगा:

Procedure printItems(Table, maxCapacity, Value):
i := Item.size - 1
j := maxCapacity
while j is not equal to 0
    if Table[i][j] is equal to Table[i-1][j]
        i := i - 1
    else
        Print: i
        j := j - weight[i]
        i := i - 1
    end if
end while

यदि हम अपना उदाहरण देते हैं, तो हम प्राप्त करेंगे:

इससे हम कह सकते हैं कि, अधिकतम मूल्य प्राप्त करने के लिए हम आइटम 2 और 3 ले सकते हैं।