DSA Interview Prep · पाठ

0/1 नैपसैक और स्थान अनुकूलन

Q: क्या “0/1 नैपसैक और स्थान अनुकूलन” पाठ निःशुल्क है?

हाँ — DSA Interview Prep अध्ययन पथ के 3 तक कोई भी पाठ, जिसमें “0/1 नैपसैक और स्थान अनुकूलन” भी शामिल है, यहाँ वेब पर पूरा पढ़ना निःशुल्क है। इसके बाद CoddyKit PRO हर पाठ अनलॉक करता है, साथ ही अंतर्निर्मित कोड संपादक और चौबीसों घंटे एआई शिक्षक के साथ इंटरैक्टिव अभ्यास भी उपलब्ध कराता है। DSA Interview Prep पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

Q: क्या DSA Interview Prep शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?

पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर DSA Interview Prep शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 1वाँ पाठ है।

Q: “0/1 नैपसैक और स्थान अनुकूलन” पाठ पूरा करने में कितना समय लगता है?

CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।

Q: क्या मैं इस DSA Interview Prep पाठ में कोड लिख और चला सकता हूँ?

हाँ। हर DSA Interview Prep पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।

0/1 नैपसैक पुनरावृत्ति प्राप्त कीजिए, 2D तालिका भरिए, फिर क्षमता को उलटे क्रम में दोहराकर इसे 1D ऐरे में घटाइए।

पाठ 1, कुल 4 में से13 चरण

0/1 नैपसैक और स्थान अनुकूलन, CoddyKit पर DSA Interview Prep का एक निःशुल्क पाठ है। यह 4 में से 1वाँ पाठ है। इस अध्ययन पथ के 3 तक कोई भी पाठ पूरा पढ़ना निःशुल्क है — इसके बाद CoddyKit PRO हर पाठ अनलॉक करता है, साथ ही अंतर्निर्मित कोड संपादक और चौबीसों घंटे एआई शिक्षक के साथ व्यावहारिक अभ्यास भी उपलब्ध कराता है। यह DSA Interview Prep सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। DSA Interview Prep पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

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

0/1 नैपसैक समस्या में: n वस्तुएँ दी गई हैं, जिनमें प्रत्येक का भार w[i] और मान v[i] है, तथा क्षमता W वाला एक नैपसैक दिया गया है। क्षमता से अधिक हुए बिना कुल मान को अधिकतम करने के लिए वस्तुएँ चुनिए। प्रत्येक वस्तु ठीक एक बार ली जाती है (0 = छोड़ना, 1 = लेना)। यह साक्षात्कारों में पूछी जाने वाली बड़ी संख्या में DP समस्याओं का आदर्श उदाहरण है, जिनमें समान-विभाजन-उपसमुच्चय-योग और लक्ष्य-योग शामिल हैं।

DP अवस्था और पुनरावृत्ति

dp[i][c] को पहले i वस्तुओं और c क्षमता का उपयोग करके प्राप्त अधिकतम मान के रूप में परिभाषित कीजिए। वस्तु i के लिए दो विकल्प हैं: इसे छोड़ दें (dp[i-1][c]) या इसे लें, यदि w[i] <= c हो (dp[i-1][c-w[i]] + v[i])। पुनरावृत्ति यह है: जब w[i] <= c हो, तब dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]); अन्यथा dp[i][c] = dp[i-1][c]। आधार स्थिति: सभी c के लिए dp[0][c] = 0।

2D DP तालिका का कार्यान्वयन

2D तालिका में (n+1) x (W+1) प्रविष्टियाँ होती हैं और प्रत्येक वस्तु के लिए इसे पंक्ति-दर-पंक्ति भरा जाता है। सभी पंक्तियाँ भरने के बाद dp[n][W] में अधिकतम मान होता है। इसमें O(n × W) समय और O(n × W) स्थान लगता है — यह छद्म-बहुपद जटिलता है, जो W छोटा होने पर प्रभावी रहती है।

def knapsack_2d(weights, values, W):
    n = len(weights)
    dp = [[0]*(W+1) for _ in range(n+1)]
    
    for i in range(1, n+1):
        w, v = weights[i-1], values[i-1]
        for c in range(W+1):
            dp[i][c] = dp[i-1][c]  # skip item i
            if c >= w:
                dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
    
    return dp[n][W]

weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
print(knapsack_2d(weights, values, 8))  # 10

1D DP के लिए क्षमता को उल्टी दिशा में क्यों चलाएँ

मुख्य अवलोकन यह है कि पंक्ति i केवल पंक्ति i-1 पर निर्भर करती है। इसलिए हम एकल 1D सरणी का उपयोग कर सकते हैं और उसी में मान अपडेट कर सकते हैं। हालाँकि, यदि हम क्षमता c को बाएँ से दाएँ (छोटी से बड़ी) चलाएँ, तो वस्तु i की दो बार गणना हो सकती है — हम c-w[i] के उस अपडेट किए गए मान का उपयोग कर सकते हैं जिसमें वस्तु i पहले से शामिल है। दाएँ से बाएँ (बड़ी से छोटी) चलाने पर प्रत्येक पंक्ति के अपडेट में हर वस्तु का उपयोग अधिकतम एक बार सुनिश्चित होता है।

# Forward iteration (WRONG for 0/1 knapsack - counts items multiple times)
# for c in range(W+1):
#     dp[c] = max(dp[c], dp[c-w] + v)   <-- dp[c-w] may already use item i

# Backward iteration (CORRECT for 0/1 knapsack)
# for c in range(W, w-1, -1):
#     dp[c] = max(dp[c], dp[c-w] + v)   <-- dp[c-w] still from previous row

1D स्थान-अनुकूलित कार्यान्वयन

केवल एक सरणी रखकर और क्षमता को W से घटाते हुए w[i] तक चलाकर, हम O(W) स्थान में 2D तालिका जैसा ही परिणाम प्राप्त करते हैं। समय जटिलता O(n × W) ही रहती है। यह स्थान-अनुकूलन याद रखना बहुत महत्वपूर्ण है — साक्षात्कारकर्ता अक्सर आपसे 2D नैपसैक को 1D में बदलने के लिए कहते हैं।

def knapsack_1d(weights, values, W):
    dp = [0] * (W + 1)
    
    for i in range(len(weights)):
        w, v = weights[i], values[i]
        for c in range(W, w - 1, -1):  # iterate RIGHT TO LEFT
            dp[c] = max(dp[c], dp[c - w] + v)
    
    return dp[W]

weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
print(knapsack_1d(weights, values, 8))  # 10

selected वस्तुओं का पुनर्निर्माण

कौन-सी वस्तुएँ selected थीं, यह जानने के लिए आपको पूरी 2D तालिका चाहिए। इसे भरने के बाद dp[n][W] से पीछे की ओर जाएँ: यदि dp[i][c] != dp[i-1][c], तो वस्तु i शामिल थी — उसके भार को c से घटाएँ और पंक्ति i-1 पर जाएँ। i = 0 तक यह प्रक्रिया जारी रखें। 1D अनुकूलन इस पुनर्निर्माण की क्षमता को हटा देता है।

def knapsack_with_items(weights, values, W):
    n = len(weights)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        w, v = weights[i-1], values[i-1]
        for c in range(W+1):
            dp[i][c] = dp[i-1][c]
            if c >= w:
                dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
    
    # Reconstruct
    selected, c = [], W
    for i in range(n, 0, -1):
        if dp[i][c] != dp[i-1][c]:
            selected.append(i-1)
            c -= weights[i-1]
    return dp[n][W], selected[::-1]

print(knapsack_with_items([2,3,4,5],[3,4,5,6],8))

व्यावहारिक उदाहरण: कुल मान को अधिकतम करना

इन वस्तुओं पर विचार कीजिए: weights=[2,3,4,5], values=[3,4,5,6], W=8। सर्वोत्तम विकल्प है: भार 3 (मान 4) और भार 5 (मान 6) वाली वस्तुएँ लें — कुल भार 8 और मान 10। या भार 2 और 5 लें — कुल मान 9। या भार 2 और 3 लें — मान 7। DP सही रूप से अधिकतम 10 ढूँढता है। ध्यान दें कि लालची विधि (सबसे अधिक मान-से-भार अनुपात वाली वस्तु लेना) पहले 1.5 अनुपात वाली वस्तु (भार 2, मान 3) लेगी — जो हमेशा सर्वोत्तम नहीं होती।

भिन्नात्मक नैपसैक बनाम 0/1 नैपसैक

भिन्नात्मक नैपसैक में आप वस्तुओं के अंश ले सकते हैं। इसे मान/भार अनुपात के आधार पर क्रमबद्ध करके लालची विधि से हल किया जा सकता है। 0/1 नैपसैक में वस्तुएँ अविभाज्य होती हैं — लालची विधि विफल होती है और DP आवश्यक होता है। साक्षात्कारकर्ता इस अंतर का उपयोग यह जाँचने के लिए करते हैं कि आपको कब लालची विधि लागू करनी चाहिए। यदि भिन्नात्मक रूप के बारे में पूछा जाए, तो तुरंत क्रमबद्ध करने वाली लालची विधि का उल्लेख करें; यदि 0/1 रूप हो, तो DP अपनाएँ।

# Fractional knapsack: greedy by value/weight ratio
def fractional_knapsack(weights, values, W):
    items = sorted(zip(values, weights), key=lambda x: x[0]/x[1], reverse=True)
    total = 0
    for v, w in items:
        if W >= w:
            total += v; W -= w
        else:
            total += v * (W / w); break
    return total

print(fractional_knapsack([2,3,4,5],[3,4,5,6],8))

छद्म-बहुपद समय जटिलता

0/1 नैपसैक NP-पूर्ण है, फिर भी हम इसे O(nW) समय में हल करते हैं। यह विरोधाभास इसलिए दूर होता है क्योंकि O(nW) छद्म-बहुपद है: W एक मान है, इनपुट का आकार नहीं। W के द्विआधारी निरूपण में O(log W) बिट लगती हैं, इसलिए वास्तविक जटिलता O(n × 2^(log W)) है, जो इनपुट के आकार के संबंध में घातांकीय है। जब W छोटा हो (जैसे, 10⁴), तब DP व्यावहारिक है; जब W 10⁹ तक हो सकता है, तब हमें अलग तरीकों की आवश्यकता होती है।

साक्षात्कारकर्ता का अनुवर्ती प्रश्न: बड़ी क्षमता

यदि साक्षात्कारकर्ता W को बहुत बड़ा (जैसे, 10⁹) रखता है, लेकिन n छोटा है, तो मानक DP विफल हो जाता है। विकल्पों में शामिल हैं: (1) O(2^(n/2) × n) समय वाली मध्य-विभाजन विधि, (2) भिन्नात्मक रूप के लिए लालची सन्निकटन, या (3) शाखा-सीमा विधि। W <= 10⁵ वाली अधिकांश साक्षात्कार समस्याओं के लिए पीछे की ओर चलने वाला 1D DP अपेक्षित उत्तर होता है।

बड़ी क्षमता के लिए मध्य-विभाजन विधि

जब W बहुत बड़ा हो लेकिन n छोटा हो (जैसे, n=40), तब मानक O(nW) DP संभव नहीं होता, जबकि पूर्ण खोज 2^n बहुत धीमी होती है। मध्य-विभाजन विधि वस्तुओं को दो हिस्सों में बाँटती है, प्रत्येक हिस्से के सभी 2^(n/2) उपसमुच्चयों की सूची बनाती है और उन्हें सर्वोत्तम ढंग से जोड़ती है। एक हिस्से को भार के अनुसार क्रमबद्ध करें, फिर दूसरे हिस्से के प्रत्येक उपसमुच्चय के लिए द्विआधारी खोज से क्षमता के भीतर सर्वोत्तम जोड़ी ढूँढें। इसमें O(2^(n/2) × n) समय लगता है — n के 40 तक होने पर यह व्यावहारिक है।

त्वरित जाँच

इस पाठ में सिखाई गई डेटा संरचनाएँ और एल्गोरिद्म — कोडिंग साक्षात्कार की तैयारी — संबंधी अवधारणाओं की अपनी समझ जाँचें।

इंटरैक्टिव पाठ में इसका उत्तर दें

पाठ का पुनरावलोकन

इस पाठ में आपने सीखा: 0/1 नैपसैक DP में dp[i][c] अवस्था i वस्तुओं और c क्षमता के साथ प्राप्त अधिकतम मान दर्शाती है, पुनरावृत्ति प्रत्येक वस्तु को छोड़ने या लेने का विकल्प चुनती है, और 1D स्थान-अनुकूलन वस्तुओं की दोहरी गणना रोकने के लिए क्षमता को दाएँ से बाएँ चलाता है। अगले पाठ में हम असीमित नैपसैक का अध्ययन करेंगे, जिसमें वस्तुओं का पुनः उपयोग किया जा सकता है, और इसे सिक्का परिवर्तन II पर लागू करेंगे।

शुरुआत निःशुल्क

एआई शिक्षक के साथ Python सीखें — निःशुल्क

अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।

पाठ्यक्रम: 30
पाठ: 120

निःशुल्क सीखना शुरू करें पूरा पाठ्यक्रम देखें

अक्सर पूछे जाने वाले प्रश्न

क्या “0/1 नैपसैक और स्थान अनुकूलन” पाठ निःशुल्क है?

हाँ — DSA Interview Prep अध्ययन पथ के 3 तक कोई भी पाठ, जिसमें “0/1 नैपसैक और स्थान अनुकूलन” भी शामिल है, यहाँ वेब पर पूरा पढ़ना निःशुल्क है। इसके बाद CoddyKit PRO हर पाठ अनलॉक करता है, साथ ही अंतर्निर्मित कोड संपादक और चौबीसों घंटे एआई शिक्षक के साथ इंटरैक्टिव अभ्यास भी उपलब्ध कराता है। DSA Interview Prep पाठ्यक्रम में कुल 4 पाठ शामिल हैं।