Space-Optimized Knapsack

पूरी सारणी के लिए n गुणा cap स्मृति चाहिए, जो बड़े आगत पर बहुत अधिक हो सकती है। स्थान अनुकूलन इसे दोबारा उपयोग की जाने वाली एक पंक्ति तक घटा देता है।

ध्यान दीजिए कि हर खाना केवल पिछली पंक्ति पढ़ता है, उससे पहले की किसी पंक्ति को नहीं। इसलिए पूरी सारणी को एक साथ सहेजने की आवश्यकता नहीं है।

cap+1 लंबाई वाली एक dp सारणी रखिए। हर वस्तु को संसाधित करते समय, नई पंक्ति दर्शाने के लिए उसी में मान बदलते जाइए।

यदि आप क्षमता पर बाएँ से दाएँ चलते हैं, तो dp[w - wt[i]] इसी वस्तु के लिए पहले ही बदल चुका हो सकता है। इससे आप वस्तु i को दो बार ले पाएँगे।

इसका समाधान है कि क्षमता पर बड़े मान से छोटे मान की ओर लूप चलाया जाए। पीछे की ओर चलने से dp[w - wt[i]] में पिछली पंक्ति का मान ही बना रहता है।

जब आप dp[w] निकालते हैं, तब छोटा सूचकांक w - wt[i] इस चरण में अभी भी अछूता रहता है, इसलिए वह अपेक्षित पिछली पंक्ति को दर्शाता है।

wt[i] से कम क्षमताओं में वस्तु नहीं समा सकती, इसलिए लूप wt[i] पर रुक जाता है। उन्हें छोड़ने से कुछ अनावश्यक चक्र बच जाते हैं।

पूरा समाधान एक सारणी पर चलने वाले दो नेस्टेड लूप हैं। बाहर वस्तुएँ, भीतर क्षमता पर पीछे की ओर चलना, और उत्तर अपने-आप मिल जाता है।

सभी वस्तुओं के बाद dp[cap] में अधिकतम मूल्य होता है। कम स्मृति में यह वही संख्या देता है जो 2D सारणी देती।

आपने एल्गोरिदम को तेज़ नहीं किया; इसमें अब भी n गुणा cap काम लगता है। आपने केवल स्मृति को द्विघाती से रैखिक कर दिया है।

जब cap बड़ा हो और 2D सारणी स्मृति-सीमा पार कर जाए, तब यह तरकीब आपको बचाती है। यह प्रतियोगिताओं में बार-बार काम आने वाली महत्वपूर्ण विधि है।

आपने 2D सारणी को एक सारणी में बदल दिया और सही परिणाम के लिए क्षमता पर पीछे की ओर लूप चलाया, यानी द्विघाती स्मृति को रैखिक स्मृति से बदल दिया। 🚀