Ratio से Fractional Knapsack
सबसे अधिक value-per-weight पहले लें
Ratio से Fractional Knapsack, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 3वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
नैपसैक की तैयारी
आपके पास मूल्य और भार वाली वस्तुएँ हैं तथा सीमित capacity वाला एक बैग है। लक्ष्य है कि आप जितना संभव हो उतना कुल मूल्य ले जा सकें। 🎒
भिन्नात्मक का अर्थ है बाँटा जा सकना
fractional रूप में आप किसी वस्तु का एक हिस्सा ले सकते हैं, जैसे अनाज की आधी बोरी। यही स्वतंत्रता यहाँ लालची विधि को सफल बनाती है।
भार के प्रति मूल्य
मुख्य माप प्रत्येक वस्तु के मूल्य और भार का ratio है। अधिक अनुपात का अर्थ है कि बहुत कम जगह में बहुत अधिक मूल्य समाया है।
ratio = value / weightसर्वोत्तम अनुपात के अनुसार sort कीजिए
वस्तुओं को मूल्य-प्रति-भार के आधार पर, सबसे अधिक से शुरू करके Sort कीजिए। लालची योजना उपलब्ध सबसे अधिक मूल्य-घनत्व वाली वस्तु लेते रहने की है।
items.sort(key=lambda i: i[0] / i[1], reverse=True)फिट होने तक पूरी वस्तु लीजिए
क्रमबद्ध सूची पर चलिए और शेष क्षमता में फिट होने पर प्रत्येक वस्तु को fully लीजिए। उसके पूरे मूल्य को अपने कुल में जोड़िए।
if weight <= cap:
total += value
cap -= weightअंतिम खाली स्थान भरिए
जब कोई वस्तु बहुत बड़ी हो, तो शेष स्थान को ठीक-ठीक भरने वाला उसका एक fraction लीजिए। फिर बैग भर जाता है और आप रुक जाते हैं।
total += value * (cap / weight)अनुपात का क्रम क्यों काम करता है
क्षमता की प्रत्येक इकाई में संभवतः सबसे अधिक मूल्य होना चाहिए, इसलिए सबसे densest वस्तु पहले जानी चाहिए। कम घनत्व वाली वस्तु से अदला-बदली करने पर केवल मूल्य का नुकसान होता है।
0/1 थैला समस्या अलग है
यदि वस्तुओं को विभाजित नहीं किया जा सकता, तो अनुपात के आधार पर लालची विधि विफल हो जाती है। 0/1 संस्करण के लिए इस सरल क्रमबद्धता के बजाय गतिशील प्रोग्रामन आवश्यक है।
चलने का समय
अनुपात के आधार पर क्रमबद्ध करने में O(n log n) समय लगता है और भरने वाला चक्र रैखिक है। सामान्य प्रतियोगिता-सीमाओं के लिए यह पर्याप्त तेज़ है।
अंतिम भिन्न पर ध्यान दें
आंशिक वस्तु के लिए दशमलव संख्याओं या सटीक परिमेय संख्याओं का उपयोग करें। जल्दी से पूर्णांक में बदलने पर मूल्य घट सकता है और गलत उत्तर आ सकता है।
यह कहाँ काम आता है
माल लादने, ईंधन मिलाने या संसाधनों को बाँटने के बारे में सोचिए। जब भी वस्तुओं के भाग किए जा सकते हों, अनुपात-आधारित लालची विधि आपका उपकरण है।
त्वरित जाँच
आप भिन्नात्मक थैला समस्या में एक थैला भर रहे हैं।
पुनरावलोकन
वस्तुओं को भार के प्रति मूल्य के आधार पर क्रमबद्ध करें, जो पूरी वस्तुएँ समा सकें उन्हें लें, फिर थैला पूरा भरने के लिए किसी वस्तु का एक भाग लें। यह लालची विधि केवल तभी सर्वोत्तम है जब वस्तुओं को बाँटा जा सके। 🚀
एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 90
- पाठ
- 360
अक्सर पूछे जाने वाले प्रश्न
क्या “Ratio से Fractional Knapsack” पाठ निःशुल्क है?
हाँ—“Ratio से Fractional Knapsack” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“Ratio से Fractional Knapsack” में मैं क्या सीखूँगा?
सबसे अधिक value-per-weight पहले लें आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 3वाँ पाठ है।
“Ratio से Fractional Knapsack” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- Greedy सोच
- सबसे जल्दी समाप्त होने वाली Activity चुनना
- Ratio से Fractional Knapsack
- Greedy कब विफल होता है पहचानें