Ratio से Fractional Knapsack
सबसे अधिक value-per-weight पहले लें
Ratio से Fractional Knapsack, CoddyKit पर Competitive Programming Academy का एक निःशुल्क पाठ है। यह 4 में से 3वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह Competitive Programming Academy सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। Competitive Programming Academy पाठ्यक्रम में कुल 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) समय लगता है और भरने वाला चक्र रैखिक है। सामान्य प्रतियोगिता-सीमाओं के लिए यह पर्याप्त तेज़ है।
अंतिम भिन्न पर ध्यान दें
आंशिक वस्तु के लिए दशमलव संख्याओं या सटीक परिमेय संख्याओं का उपयोग करें। जल्दी से पूर्णांक में बदलने पर मूल्य घट सकता है और गलत उत्तर आ सकता है।
यह कहाँ काम आता है
माल लादने, ईंधन मिलाने या संसाधनों को बाँटने के बारे में सोचिए। जब भी वस्तुओं के भाग किए जा सकते हों, अनुपात-आधारित लालची विधि आपका उपकरण है।
त्वरित जाँच
आप भिन्नात्मक थैला समस्या में एक थैला भर रहे हैं।
पुनरावलोकन
वस्तुओं को भार के प्रति मूल्य के आधार पर क्रमबद्ध करें, जो पूरी वस्तुएँ समा सकें उन्हें लें, फिर थैला पूरा भरने के लिए किसी वस्तु का एक भाग लें। यह लालची विधि केवल तभी सर्वोत्तम है जब वस्तुओं को बाँटा जा सके। 🚀
एआई शिक्षक के साथ Python सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 30
- पाठ
- 120
अक्सर पूछे जाने वाले प्रश्न
क्या “Ratio से Fractional Knapsack” पाठ निःशुल्क है?
हाँ—“Ratio से Fractional Knapsack” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और Competitive Programming Academy पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। Competitive Programming Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“Ratio से Fractional Knapsack” में मैं क्या सीखूँगा?
सबसे अधिक value-per-weight पहले लें आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ Competitive Programming Academy का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या Competitive Programming Academy शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर Competitive Programming Academy शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 3वाँ पाठ है।
“Ratio से Fractional Knapsack” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस Competitive Programming Academy पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर Competitive Programming Academy पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- Greedy सोच
- सबसे जल्दी समाप्त होने वाली Activity चुनना
- Ratio से Fractional Knapsack
- Greedy कब विफल होता है पहचानें