कोडिंग साक्षात्कार की तैयारी · पाठ

0/1 Knapsack: लें या छोड़ें

weight cap के भीतर value अधिकतम करें

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

0/1 Knapsack: लें या छोड़ें, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 1वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

थैला-समस्या की कहानी

आपके पास भार सीमा वाला एक थैला और वस्तुओं का ढेर है। 0/1 थैला-समस्या पूछती है: थैला ज़रूरत से अधिक भरे बिना कौन-सी वस्तुएँ अधिकतम मूल्य देंगी? 🎒

लें या छोड़ें

0/1 का अर्थ है कि हर वस्तु या तो पूरी तरह ली जाती है या पूरी तरह छोड़ दी जाती है। आप किसी वस्तु का आधा भाग नहीं ले सकते, इसलिए हर विकल्प हाँ या नहीं होता है।

लालची विधि क्यों विफल होती है

सबसे सस्ती या सबसे मूल्यवान वस्तु पहले लेने से क्षमता व्यर्थ जा सकती है। यहाँ लालची शॉर्टकट काम नहीं करता, इसलिए वास्तविक संयोजनों पर विचार करना पड़ता है।

दो दी गई सूचियाँ

आपको दो समानांतर सूचियाँ दी गई हैं: हर वस्तु का भार और मूल्य, साथ में एक क्षमता। वस्तु i का भार wt[i] और मूल्य val[i] है।

wt  = [1, 3, 4, 5]
val = [1, 4, 5, 7]
cap = 7

अवस्था परिभाषित करें

मान लीजिए dp[i][w], पहली i वस्तुओं को w क्षमता में रखकर मिलने वाला सर्वोत्तम मूल्य है। अवस्था का सटीक नामकरण ही पूरी समस्या का केंद्र है।

छोड़ने का विकल्प

यदि आप वस्तु i को छोड़ते हैं, तो आपका मूल्य वही रहेगा जो पहले से था: dp[i-1][w]। बाकी वस्तुओं के लिए क्षमता में कोई बदलाव नहीं होगा।

लेने का विकल्प

यदि आप वस्तु i को लेते हैं, तो उसका मूल्य जोड़कर क्षमता घटाइए: val[i] + dp[i-1][w - wt[i]]। यह तभी मान्य है जब w, wt[i] से कम न हो।

बेहतर शाखा चुनें

पुनरावृत्ति-सूत्र max की सहायता से दोनों विकल्पों में से बड़े को रखता है। हर खाना अपने नीचे पहले से निकाले गए उत्तरों पर भरोसा करता है।

dp[i][w] = max(dp[i-1][w],
               val[i] + dp[i-1][w - wt[i]])

आधार पंक्ति

शून्य वस्तुओं के साथ आप किसी भी क्षमता में शून्य मूल्य ही ले जा सकते हैं। यही आधार स्थिति पहली पंक्ति को सभी शून्यों से भरती है, जिस पर आगे का काम आधारित होता है।

dp = [[0] * (cap + 1) for _ in range(n + 1)]

सारणी भरें

बाहरी लूप में वस्तुओं और भीतरी लूप में क्षमताओं पर चलिए। हर खाना केवल ऊपर वाली पंक्ति पढ़ता है, इसलिए एक ही क्रम में सब कुछ भर जाता है।

for i in range(1, n + 1):
    for w in range(cap + 1):
        dp[i][w] = dp[i-1][w]

उत्तर पढ़ें

निचले-दाएँ खाने dp[n][cap] में सभी वस्तुओं और पूरी क्षमता के लिए अधिकतम मूल्य होता है। यही एक खाना आपका अंतिम उत्तर है।

त्वरित जाँच

मुख्य 0/1 थैला-समस्या के पुनरावृत्ति-सूत्र की जाँच कीजिए।

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

पुनरावृत्ति

आपने 0/1 थैला-समस्या सीखी: हर वस्तु को लेना या छोड़ना होता है, dp[i][w] छोड़ने और लेने में से बेहतर विकल्प रखता है, और dp[n][cap] उत्तर होता है। 🎉

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

एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क

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

पाठ्यक्रम: 90
पाठ: 360

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

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

क्या “0/1 Knapsack: लें या छोड़ें” पाठ निःशुल्क है?

हाँ—“0/1 Knapsack: लें या छोड़ें” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

“0/1 Knapsack: लें या छोड़ें” में मैं क्या सीखूँगा?

weight cap के भीतर value अधिकतम करें आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।

क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?

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

“0/1 Knapsack: लें या छोड़ें” पाठ पूरा करने में कितना समय लगता है?

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

क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?

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

इस पाठ्यक्रम के सभी पाठ

← कोडिंग साक्षात्कार की तैयारी पर वापस जाएँ