1. Introduction and Greedy Algorithm Basics
Video introduction covering the syllabus for greedy and dynamic programming, followed by the definition of greedy algorithms with a simple currency note example.
सो हे गाइस वेलकम बैक टू माय चैनल एक्स ऑफिशियल एंड यस इन दिस वीडियो आई एम गोइंग टू कवर योर डायिट थ्री दैट इज ग्रीडी एंड डायनामिक प्रोग्रामिंग। ठीक है?इस पर्टिकुलर वीडियो के अंदर आपको सारे के सारे कांसेप्ट्स क्लियर होंगे। प्लस आपको सेवन प्रीवियस ईयर क्वेश्चन पेपर्स का स्यूशन भी समझाया जाएगा। हर कांसेप्ट के बाद उससे रिलेटेड 2022 से 2025 तक मई, जून हो या नवंबर दिसंबरहो सारे के सारे पीवाईक्यूस के सशंस हैं। एंड दैट आई एम गोइंग टू एक्सप्लेन यू। चाहे वो न्यूमेरिकल हो या थ्यरी हो। तो प्लीज वीडियो को जरूर से लाइक कर देना एंड पूरे फोकस के साथ पढ़ने बैठना। इसवीडियो के लिए काफी ज्यादा मेहनत लगी है। तो प्लीज प्लीज लाइक कर देना एंड अपने ओपिनियंस कमेंट सेक्शन में जरूर देना। तो चलिए विदाउट वेस्टिंग आवर टाइम लेट्स स्टार्ट विद द थिंग एंड एंड ये नोट्स अगर आपको चाहिए
तो आप एचके ऑफिशियल डॉटin वेबसाइट के ऊपर जाके डा नोट्स परचेस कर सकते हो एंड आपको सारे के सारे एनएम रिलेटेड नोट्स यूनिट थ्री से यूनिट सिक्स तक सब अवेलेबल है तो आप वहां से जाके रिवीजन कर सकतेहो ठीक है नाउ मेन टॉपिक पर आ जाते हैं। ये है आपका पूरा का पूरा सिलेबस जो हम इस वीडियो में कवर करेंगे। पार्ट ए है आपका ग्रीडी स्ट्रेटजी। इसके अंदर ये सारी चीजें हैं। देन आपके पास डायनामिकप्रोग्रामिंग है। एंड देन ये सारे के सारे पीवाईक्यूस हैं जो कि हम कवर करेंगे। तो दिस इज़ जस्ट अ ग्लिं्स। नाउ लेट अस स्टार्ट विद द ग्रीडी स्ट्रेटजी। ओके?सो देखो सबसे पहले समझना है कि ग्रीडी एल्गोरिदम क्या होता है। ठीक है?नाम से ही समझ आ रहा है ग्रीडी। ग्रीडी का मतलब लालची। ओके?तो ग्रीडी एल्गोरिदम में हम हर स्टेप पर वो ऑप्शन चूज़ करते हैं जो उस मोमेंट पर सबसे ज्यादा बेस्ट लगता है। क्लियर?
तो और एक बार चॉइस अगर आपको करनी है। आपने एक बार बेस्ट चूज़ कर लिया उसके बाद आप उसको चेंज नहीं कर सकते। ठीक है?तो बस आपको ये चीज अच्छे से याद रखनी है। एकदम सिंपल एग्जांपल के साथ इसको समझते हैं। सप सपोज़ आपको ₹80 देने हैं। ठीक है?और आपके पास है ₹50, ₹20, 10, 5 और वन। ठीक है?ये सारे आपके पास नोट्स हैं। अब तुम्हें मिनिमम नंबर ऑफ नोट्स यूज़ करने हैं। तो सबसे पहले क्या करोगे मुझे बताओ?ऑब्वियसली जो सबसे बड़ा नोट होगा वो आप चूज़ करोगे। तो 80 से छोटा या इक्वल होना चाहिए वो। तो सबसे पहला आपके पास है 50। तो आप ₹50 ले लोगे। बचे आपके पास कितने?30। क्लियर?फिर आप क्या करोगे?₹20 लोगे। तो अब कितने बचे?10:00 बजे। फिर आप ₹10 लोगे एंड अब कुछ नहीं बचा। सो टोटल जो है नोट्स आपके पास कितने हुए?
तीन नोट्स हुए 50 का, 20 का, 10 का। तो टोटल आपके पास ₹80 हो गए। तो यही है ग्रीडी अप्रोच। हर स्टेप पर बेस्ट अवेलेबल चॉइस आपको लेनी होती है और आगे बढ़ना होता है। क्लियर?तो ग्रीडी यानी कि बेस्ट चॉइस एट एव्री स्टेप। आई होप आपको अच्छे से समझ में आ गया है। नाउ लेट अस कम ऑन टू द इंपॉर्टेंट टर्म्स। ओके?
2. Important Terms and Greedy Properties
Explains objective function, feasible solution, optimal solution, selection and feasibility functions, plus greedy choice property and optimal substructure with a flowchart.
तो एग्जाम्स में ये टर्म्स आपको पूछे जा सकते हैं। बहुत ज्यादा सिंपल लैंग्वेज में मैं आपको एक्सप्लेन करती हूं। सबसे पहला है ऑब्जेक्टिव फंक्शन। ऑब्जेक्टिव फंक्शन मतलब हमें अचीव क्या करना है?मैक्सिमम या मिनिमम। जैसे मैक्सिमम प्रॉफिट चाहिए, मिनिमम कॉस्ट चाहिए या फिर मिनिमम नंबर ऑफ़ एक्टिविटीज चाहिए। तो, यह आपको पता चलता है ऑब्जेक्टिव फंक्शन से। सेकंडली आपके पास है फिजिबल सॉल्यूशन। फज़िबल सॉल्यूशन मतलब ऐसा सॉल्यूशन जो प्रॉब्लम कीसारी कंडीशंस फॉलो करता है। फॉर एग्जांपल बैग की कैपेसिटी 10 kg है तो उसमें आप 12 kg तो नहीं डाल सकते। राइट?तो सॉल्यूशन फिजिबल होना चाहिए। क्लियर?थर्ड आपके पास है ऑप्टिमल सॉल्यूशन। ऑप्टिमल सॉल्यूशन का मतलब है सारे वैलिड सॉलशंस में से सबसे बेस्ट सॉल्यूशन। अगर मैक्सिमम प्रॉफिट चाहिए तो जिस सॉल्यूशन से सबसे ज्यादा प्रॉफिट मिलेगा वो ऑप्टिमल सॉल्यूशन हो गया आपका। क्लियर?देन फोर्थ आपके पास है सिलेक्शन फंक्शन। सिलेक्शन फंक्शन डिसाइड करता है कि नेक्स्ट कौन सा ऑप्शन चूज़ करना है। फॉर एग्जांपल सबसे ज्यादा प्रॉफिट वाला आइटम कौन सा है। ठीक है?
वो आपको चूज़ करना है। फिफ्थ आपके पास है फिजिबिलिटी फंक्शन। फजिबिलिटी फंक्शन चेक करता है कि जो ऑप्शन हम चूज़ कर रहे हैं वो कंडीशंस सेटिस्फाई करता है या नहीं। ठीक है?तो ये पांचों भी टर्म्स मैंने आपको बहुत इजीली एक्सप्लेन कर दिए। देन आपके पास आती हैं दो इंपॉर्टेंट प्रॉपर्टीज। तो ग्रीडी एल्गोरिदम को एकदम करेक्टली वर्क करने के लिए दो इंपॉर्टेंट प्रॉपर्टीज होती हैं। फर्स्ट आपके पास है ग्रीडीचॉइस प्रॉपर्टी। सेकंड आपके पास है ऑप्टिमल सबस्ट्रक्चर। ठीक है?तो ग्रीबी ग्रीडी चॉइस प्रॉपर्टी की अगर मैं बात करूं तो इसका मतलब है कि हर स्टेप पर लोकली बेस्ट चॉइस करके हम ग्लोबली बेस्ट स्यूशन तक पहुंचवा पहुंच सकते हैं। ठीक है?अब सिंपल वर्ड्स में अगर मैं आपको बताऊं तो हर स्टेप का बेस्ट डिसीजन मिलकर फाइनल बेस्ट आंसर दे सकता है। एंड दैट इज योर ग्रीडी चॉइस प्रॉपर्टी। ओके?सेकंड अगर हम ऑप्टिमल सबस्ट्रक्चर की बात करें तो इसका मतलब है कि बड़े प्रॉब्लम का ऑप्टिमल सॉल्यूशन तो उसके स्मॉलर सब प्रॉब्लम्स के ऑप्टिमल सॉलशंस जो है उनसे बन सकता है। है ना?
तो याद रखना ग्रीडी चॉइस प्रॉपर्टी प्लस ऑप्टिमल सबस्ट्रक्चर दीज़ आर द टू इंपॉर्टेंट प्रॉपर्टीज ऑफ ग्रीडी एल्गोरिदम। ओके?ओके तो आई होप मैंने ये दो चीजें आपको बहुत क्लियर कर दी है। ओके नाउ ये आपको फ्लो चार्ट समझना है। इससे आप समझ जाओगे कि ग्रीडी एल्गोरिदम कैसे काम करती है। सबसे पहले एम्प्टी सॉल्यूशन से स्टार्ट करतेहैं। फिर बेस्ट कैंडिडेट चूज़ करते हैं। चेक करते हैं कि कैंडिडेट वैलिड है या नहीं। अगर वैलिड है तो सलूशन में ऐड कर दो। और अगर वैलिड नहीं है तो उस कैंडिडेट को डिस्कार्ड कर दो। फिर नेक्स्ट कैंडिडेटचेक करो। जब सारे कैंडिडेट्स चेक हो जाए तो फाइनल स्यूशन रिटर्न कर दो। बस गाइस ग्रीडी प्रिंसिपल इतना ही है। एक लाइन में याद रखो। चूज़ द बेस्ट अवेलेबल ऑप्शन एट एव्री स्टेप एंड नेवर लुक बैक। ओके?लेकिन एक इंपॉर्टेंट बात ग्रीडी एल्गोरिदम हर प्रॉब्लम में करेक्ट आंसर नहीं देता। हमें प्रूफ करना होता है कि उस प्रॉब्लम के लिए ग्रीडी चॉइस से ऑप्टिमल स्यूशन मिलता है। ठीक है?
सो आई होप यू अंडरस्टुड अबाउट दिस। नाउ लेट अस मूव ऑन टू द नेक्स्ट थिंग। हियर यू हैव ग्रीडी कंट्रोल एब्स्ट्रैक्शन एंड टाइम एनालिसिस। ठीक है?
3. Greedy Control Abstraction and Time Analysis
Covers the greedy control abstraction algorithm with select, feasible and union functions, time complexity analysis including sorting cases, and related previous year questions.
अब यहां पर ये नाम थोड़ा टेक्निकल है बट कांसेप्ट बहुत सिंपल है। सी कंट्रोल एब्स्ट्रैक्शन मतलब एक जनरल टेंप्लेट जो बताता है कि ग्रीडी एल्गोरिदम कैसे वर्क करता है। ओके?सो अलग-अलग प्रॉब्लम्स में चॉइससेस अलग होंगी। तो लेकिन जो बेसिक स्टेप्स होते हैं वो तो ऑलमोस्ट सेम ही रहते हैं। सो ये है आपका कंट्रोल एब्स्ट्रैक्शन। चलो इसका एल्गोरिदम देखते हैं। सो यहां पर आपको ये कुछ एल्गोरिदम दिखरही है। सी इसको बिल्कुल कॉम्प्लिकेट मत करना। बहुत सिंपल है। सबसे पहले हम एक एम्प्टी सॉल्यूशन से स्टार्ट करते हैं। फिर लूप के थ्रू कैंडिडेट्स को एक-एक करके चेक करते हैं। यहां तीन इंपॉर्टेंट फंक्शनंस हैं जो आपको बहुतज्यादा अच्छे से याद रखने हैं। रिमेंबर सबसे पहला फंक्शन है आपका सेलेक्ट फंक्शन। ठीक है?ये फंक्शन जो है ये नेक्स्ट बेस्ट कैंडिडेट चूज़ करता है। फॉर एग्जांपल फ्रैक्शनल नैप्सक है जो हम आगे जाके पढ़ेंगे समझेंगे। फ्रैक्शनल लैप्सक में हम हाईएस्ट प्रॉफिट टू वेट रेशो वाला जो ऑब्जेक्ट है वो चूज़ करते हैं। तो
ये जो सिलेक्शन का जो काम है ये आपका सेलेक्ट फंक्शन कर रहा होता है। ठीक है?सेकंड जो इंपॉर्टेंट फंक्शन है वो है फिजिबल फंक्शन जिसमें हम सॉल्यूशन कॉमा x करके पास करते हैं। यहां पर ये चेक करता है कि सिलेक्टेड ऑब्जेक्ट को सॉल्यूशन में ऐड कर सकते हैं या नहीं। फॉर एग्जांपल बैग कीकैपेसिटी 10 केg है। जैसे मैंने बोला और बैग में ऑलरेडी अगर 8 kg समान है तो अगर नेक्स्ट ऑब्जेक्ट का वेट 5 kg है तो पूरा ऑब्जेक्ट ऐड नहीं कर सकते। ठीक है?ये हो गया आपका सेकंड फंक्शन। थर्ड फंक्शन है यूनियन फंक्शन एंड इसमें भी आप सॉल्यूशन कॉमा x करके पास करते हो। ये सिलेक्टेड ऑब्जेक्ट को फाइनल सॉल्यूशन में ऐड करता है और सॉल्यूशन अपडेट करता है। सो फाइनली जबसारे कैंडिडेट्स चेक हो जाते हैं तो एल्गोरिदम फाइनल सॉल्यूशन रिटर्न कर देता है। बस सेलेक्ट करो फिजिबिलिटी चेक करो और अगर वैलिड है तो स्यूशन में ऐड कर दो। तो प्लीज इस चीज को याद रखो। सेलेक्ट देन फिजिबल
देन यूनियन एंड देन आप रिटर्न करते हो। ठीक है?तो एग्जाम में अगर कंट्रोल एब्स्ट्रैक्शन लिखते वक्त ये एल्गोरिदम और तीनों फंक्शनंस आपके दिमाग में आए तो प्लीज प्लीज जरूर लिखना। ठीक है?ओके?अब आता है टाइम कॉम्प्लेक्सिटी। ठीक है?तो ग्रीडी एल्गोरिदम के अंदर यहां पर अगर मैं बात करूं सी एकदम सिंपल लैंग्वेज में ग्रीडी एल्गोरिदम में लूप n टाइम्स रन करता है। ठीक है?और हर आइटरेशन में सेलेक्ट फिजिबल और यूनियन फंक्शनंस कॉल होते हैं। इसीलिए तो टोटल टाइम कॉम्प्लेक्सिटी का फार्मूला होता है जो आपको स्क्रीन पे नजर आ रहा है। समेशन ऑफ़ i = 1 से लेके n तक एंड आपकेटाइम है किसका देखो सेलेक्ट फंक्शन का। फिर फिजिबल का और फिर यूनियन का। देखो बहुत सिंपल है। इसको देखकर बिल्कुल मत डरो। इसका मीनिंग बहुत सिंपल है। सेलेक्ट का टाइम, फिजिबल का टाइम और यूनियन का टाइम ऐड करनाहै। बस फिर ये प्रोसेस जो है वो n टाइम्स रिपीट होता है। ठीक है?
सो इसीलिए अगर तीनों फंक्शनंस का टाइम कांस्टेंट है तो ओवरऑल टाइम कॉम्प्लेक्सिटी जो है वो बिग ओ ऑफ़ n होगी। ओके?लेकिन अगर सिलेलेक्ट फंक्शन हर बार सारे रिमेनिंग कैंडिडेट सर्च करता है तो टाइम कॉम्प्लेक्सिटी बिग ओ ऑफ़ n² तक जा सकती है। क्लियर?सो आई होप यू अंडरस्टुड अबाउट दिस। सो यही चीजें यहां पर सॉर्टेड और अनसॉर्टेड के बारे में लिखी हुई है। क्लियर?अब अगर मैं आपको सॉर्टिंग वाला केस समझाऊं। बहुत ज्यादा इंपॉर्टेंट केस है ये। सो अगर हम कैंडिडेट्स को पहले ही सॉर्ट कर देते हैं तो सॉर्टिंग का टाइम होता है। राइट?दैट इज बिग ओ ऑफ़ n लॉग n इसको हम बोलते हैं। उसके बाद अगर हर कैंडिडेट को प्रोसेस करने में बिगो ऑफ़ वन टाइम लगता है तो प्रोसेसिंग का टोटल टाइम बिगो ऑफ़ n हो जाएगा। तो इसीलिए तोहमारी जो टाइम कॉम्प्लेक्सिटी है वो बिगो ऑफ़ n लॉग n + बिगो ऑफ़ n होगी। इसीलिए इसको हम लोग फाइनली क्या बोलते हैं?
बिगो ऑफ़ n लॉग n। ठीक है?याद रखना बिगो ऑफ़ n log n सॉर्टिंग की वजह से ही आता है। ओके?नाउ डिफरेंट ग्रीडी प्रॉब्लम्स की जो कॉम्प्लेक्सिटी है वो अलग हो सकती है। तो जो फ्रैक्शनल नैप्सक है उसकी टाइम कॉम्प्लेक्सिटी बिगो ऑफ़ n लॉग n है। ठीक है?जॉब सीक्वेंसिंग विद डेडलाइंस है उसकी कॉमनली बिगो ऑफ़ n² होती है बेसिक इंप्लीमेंटेशन के अंदर। एक्टिविटी सिलेक्शन की बात करें तो बिगो ऑफ़ n लॉग n होती है। इफ सॉर्टिंग इज़ रिक्वायर्ड एंड अगर सॉर्टिंग रिक्वायर्ड नहीं है। इफइट इज़ ऑलरेडी सॉर्टेड तो बिगो ऑफ़ n होती है। ठीक है?देन क्रिस मिनिमम स्पैनिंग ट्री की बात करें तो बिगो ऑफ़ ई लॉग बी ओके तो एग्जाम में अगर क्वेश्चन आए तो उसके अकॉर्डिंग आपको कॉम्प्लेक्सिटी लिखनी पड़ेगी। ठीक है?और इंपॉर्टेंट ट्रिक जहां पर भी सॉर्टिंग है वहां कॉमनली बिगो ऑफ़ एंड लॉग एंड टाइम कॉम्प्लेक्सिटी होती है। लेकिन फाइनल कॉम्प्लेक्सिटी इंप्लीमेंटेशन पर डिपेंड करती है। सो इसलिए बाइंडली ब्लाइंडली जो है ना ग्रीडी एल्गोरिदम की कॉम्प्लेक्सिटी बिगो ऑफ़
n log n मत लिखना। क्लियर?आई होप यू अंडरस्टुड। नाउ यहां पर ये पीवाईक्यू आ गया। जैसे मैंने आपको प्रॉमिस किया था सेवन इयर्स के पीवाईक्यूस के सारे के सारे क्वेश्चन इस पीडीएफ के अंदर है। एंड हम सारे के सारे डिस्कस करने वाले हैं।तो आई एम हियर टू एक्सप्लेन यू अबाउट दिस। ठीक है?यहां पर ये बहुतेंट क्वेश्चन है। देखो इसमें आपको कंट्रोल एब्स्ट्रैक्शन के बारे में पूछा गया है। मई जून 2024 के अंदर राइट अ कंट्रोल एब्स्ट्रैक्शन फॉर ग्रीडी मेथड एंड कमेंट ऑन द टाइम कॉम्प्लेक्सिटी ऑफ़ दिस एब्स्ट्रैक्शन। तो येतो अभी हमने ऊपर ही देख लिया। मैंने आपको दोनों भी चीजें बहुत अच्छे से एक्सप्लेन कर दी। आई होप कि अब आपको जो है ना इस क्वेश्चन के अंदर कॉन्फिडेंस आ गया होगा। सेकंड देख लो नवंबर दिसंबर 2023के पेपर के अंदर आपको पूछा गया है एक्सप्लेन ग्रीडी स्ट्रेटजी प्रिंसिपल कंट्रोल एब्स्ट्रैक्शन टाइम एनालिसिस ऑफ़ कंट्रोल एब्स्ट्रैक्शन विद सूटेबल एग्जांपल। तो देखो इसका स्यूशन मैंने बहुत शॉर्ट में लिखा है। ठीक है?
ये आपको बिल्कुल नहीं लिखना है। इतना छोटा आपको ये जस्ट मैंने एज अ समरी दिया हुआ है। तो ये आप अच्छे से लिख लो। बाकी ये जो दो पेज है इनको अच्छे से रिवाइज करना एंड एग्जाम में इन्हींका जो है ना यूज़ करके आपको लिखना है। आई होप ग्रीडी स्ट्रेटजी आपको बहुत ज्यादा क्लियर हो गई होगी। नाउ लेट अस मूव ऑन टू वेरी इंपॉर्टेंट टॉपिक दैट इज़ नैप सैक प्रॉब्लम। अब याद रखो नैप सैक का
4. Knapsack Types and Mathematical Formulation
Introduces fractional and 0/1 knapsack problems, their differences, and solves the May-June 2025 question on mathematical formulations of both variants.
मतलब होता है बैग। ओके?सपोज तुम्हारे पास एक बैग है और उसकी मैक्सिमम कैपेसिटी 10 kg है। तो तुम्हारे पास डिफरेंट ऑब्जेक्ट्स हैं। हर ऑब्जेक्ट का वेट भी है और प्रॉफिट भी है। अब तुम्हें बैग में ऑब्जेक्ट्स ऐसे सिलेलेक्ट करने हैं कि टोटलप्रॉफिट मैक्सिमम हो। लेकिन बैग की कैपेसिटी एक्सीड नहीं होनी चाहिए। बस इसी को बोलते हैं नैप्सक प्रॉब्लम। ठीक है?टू टाइप्स ऑफ नैप्सक होते हैं। यहां पर नैप्सक प्रॉब्लम के दो इंपॉर्टेंट टाइप्स हैं। सबसे पहला है आपके पास फ्रैक्शनल नैप्सक और सेकंड है आपके पास जीरो स्लश वन नैप्सक। ठीक है?तो जो फ्रैक्शनल नैप्सक है इसमें तुम ऑब्जेक्ट का कुछ पार्ट भी ले सकते हो। जैसे 1 केजी हो गया। ठीक है?1 केg शुगर है सपोज। तो तुम 500 ग्राम शुगर भी ले सकते हो। इसलिए इस प्रॉब्लम में ग्रीडी एल्गोरिदम यूज़ कर सकते हैं। ओके?और सेकंड जो है 0 वन मैप्सक इसमें ऑब्जेक्ट को या तो पूरा लेना है या बिल्कुल भी नहीं लेना है। ठीक है?
जैसे सपोज लैपटॉप है इसको आप आधा तो नहीं ले सकते। राइट?इसीलिए 0 वन नैप्सक में स्टैंडर्ड अप्रोच डायनेमिक प्रोग्रामिंग होती है। ठीक है?आई होप यू अंडरस्टुड। तो सिंपल इतना डिफरेंस याद रखो। एकदम बेसिक डिफरेंस मैं आपको समझा रही हूं। फ्रैक्शनल नैप्सक के अंदर ऑब्जेक्ट का पार्ट आप ले सकते हो। और जीरो वन नैप्सक के अंदर ऑब्जेक्ट पूरा लोगे या तोबिल्कुल नहीं लोगे। फ्रैक्शनल नैप्सक के अंदर ग्रीडी एल्गोरिदम यूज़ होती है। जीरो वन नैप्सक के अंदर डायनेमिक प्रोग्रामिंग यूज़ होती है। फ्रैक्शनल नैप्सक के अंदर रेश्यो के अकॉर्डिंग आप सेलेक्ट करते हो। और जीरो वन नैप्सक के अंदर डीपीका टेबल आप क्रिएट करते हो एंड उससे ऑप्टिमल सॉल्यूशन निकलता है। ठीक है?और अगर मैं लास्टली टाइम कॉम्प्लेक्सिटी की बात करूं तो फ्रैक्शनल नैप्सक के अंदर बिगो ऑफ़ n लॉग n कॉमन कॉम्प्लेक्सिटी होती है। और 0 वन नैप्सक की मैं बात करूं तो यहां पर बिगो ऑफ़ n डब्लू जो है
वो कॉमन कॉम्प्लेक्सिटी होती है। ठीक है?बस ये डिफरेंस बेसिक डिफरेंस याद रखना। ठीक है?सिंपल क्या है?फ्रैक्शनल मतलब कि पार्ट्स अलाउड है। 0 वन मीन्स या तो आप कंप्लीट लोगे या फिर बिल्कुल भी नहीं लोगे। है ना?बहुत सिंपल है। अब देखो ये मई जून 2025 एकदम रीसेंट एकदम रीसेंट क्वेश्चन था कि गिव अ मैथमेटिकल फॉर्मुलेशन फॉर फ्रैक्शनल नैप्सक प्रॉब्लम एंड जीरो वन नैप्सक प्रॉब्लम। अब देखो ये दिखने में आपको बहुत स्केरी लगेगा लेकिन दोमिनट बाद आप इसको एकदम इजी समझोगे। एकदम ध्यान से समझना। देखो ये क्वेश्चन इंपॉर्टेंट है क्योंकि दोनों फॉर्मूलेशंस ऑलमोस्ट सेम है। सिर्फ एक मेन कंस्ट्रेंट जो है वो यहां पे आपको चेंज करना है। ठीक है?अब इस क्वेश्चन को सुपर इजी बना देते हैं। देखो सबसे पहले आप सिंबल्स समझो। क्या है आपके पास?n है। n क्या है?टोटल नंबर ऑफ़ ऑब्जेक्ट्स। pi है। pi यानी कि ऑब्जेक्ट का प्रॉफिट। ठीक है?
wi है दैट इज योर ऑब्जेक्ट का वेट। m है आपके बैग की मैक्सिमम कैपेसिटी। XI है आपके ऑब्जेक्ट का कितना पार्ट हम ले रहे हैं। ओके?अब हमें मैक्सिमम प्रॉफिट चाहिए। तो ऑब्जेक्टिव फंक्शन यूज़ यूज़ होगा। याद करो हमने ऑब्जेक्टिव फंक्शन पढ़ा था। ठीक है?अब ये जो ऑब्जेक्टिव फंक्शन आपको दिख रहा है वो यही है। क्या?जिसके पास मैक्सिमाइज लिखा हुआ है। समेशन ऑफ़ i = 1 से n तक pi xi। इसका मतलब है हर ऑब्जेक्ट का प्रॉफिट मल्टीप्लाई करो उसके सिलेक्टेड फ्रैक्शन से और सबको ऐड कर दो। फॉर एग्जांपल किसी ऑब्जेक्ट का प्रॉफिट₹100 है और तुम उसका हाफ पार्ट लेते हो तो प्रॉफिट होगा कितना?100 * 0.5 दैट इज योर ₹50 क्लियर?अब कंस्ट्रेंट नंबर वन की बात करते हैं जो है आपका वेट। अब बैग की कैपेसिटी एक्सीड नहीं होनी चाहिए। इसलिए टोटल वेट का फार्मूला देख लो। आपके पास क्या लिखा है?
व्हिच इज़ सब्जेक्ट टू समेशन ऑफ़ i = 1 wi xi व्हिच इज़ लेस दैन इक्वल टू m इसका मतलब क्या है?हर ऑब्जेक्ट का वेट मल्टीप्लाई करो उसके सिलेक्टेड फ्रैक्शन से। फिर सबका टोटल करो। ठीक है?ये टोटल बैग की कैपेसिटी m से कम या इक्वल होनी चाहिए। दैट्स इट। अब फ्रैक्शनल नैप्सक के अंदर यहां पे जो ऑब्जेक्ट है ये क्या है?ऑब्जेक्ट का पार्ट अलाउड होता है। ये मैंने आपको बताया है। है ना?फ्रैक्शनल में हम ऑब्जेक्ट का पार्ट ले सकते हैं। नैप्स 0 वन नैप्सक के अंदर हम या तो पूरा लेंगे या फिर बिल्कुल नहीं लेंगे। है ना?तो फ्रैक्शनल नैप्सक में अगर हम ऑब्जेक्ट का पार्ट अलऊ रखते हैं। इसीलिए x ऑफ़ i की वैल्यू अगर आप फोकस करो तो x ऑफ़ i की वैल्यू जीरो से वन के बीच कुछ भी हो सकती है। है ना?देखो x ऑफ़ i की वैल्यू क्या है?
0 से वन के बीच में कुछ भी हो सकती है। है ना बहुत ज्यादा सिंपल?ओके। मतलब ऑब्जेक्ट नहीं लिया तो जीरो यहां पर लिखना है। हाफ लिया तो 0.5 लिखना है। पूरा लिया तो आपको वन लिखना है। अब ये पूरी की पूरी चीज हो गई फ्रैक्शनल नैप्सक की। अब आ जाओ जीरो वननैप्सक के ऊपर। यहां पर जो है हमें पता है कि ऑब्जेक्ट का पार्ट अलाउड नहीं है। इसीलिए x ऑफ़ i की वैल्यू अगर आप फोकस करो तो सिर्फ या तो ज़ीरो होगी या फिर वन होगी। यहां पर बीचका कोई सिस्टम नहीं है। क्लियर?तो x ऑफ i बिलोंग्स टू 0 और 1 0 मींस ऑब्जेक्ट नहीं लिया और वन मींस पूरा ऑब्जेक्ट ले लिया। ठीक है?तो दोनों भी फॉर्मुलेशंस में ऑब्जेक्टिव फंक्शन सेम है। वेट कंस्ट्रेंट सेम है। सिर्फ x ऑफ़ i की कंडीशन डिफरेंट है। याद रखो फ्रैक्शनल नैप्सक के अंदर xi आपका ज़ीरो से वन के बीच में कुछ भी हो सकता है।
और ज़ीरो वन नैप्सक के अंदर या तो ज़ीरो होगा या वन होगा। बस एग्जाम में इतना ही डिफरेंस आपको एक्सपेक्टेड था। एंड आप देख सकते हो ये मई जून 2025 का पेपर है। है ना?
5. Fractional Knapsack Algorithm and PYQ
Explains the profit/weight ratio greedy choice, the fractional knapsack algorithm, and solves the May-June 2024 numerical using the greedy method.
बहुत ज्यादा रीसेंट पेपर है। तो आई होप आपको यह बहुत अच्छे से समझ में आ गया है। ओके नाउ नाउ दिस इज़ वेरीेंट। सबसे पहले हम यहां पर फ्रैक्शनल नैप्सक को वापस समझ लेते हैं। यहां पर हमें क्याबोला गया है?यहां पर सपोज़ अगर हम इस फ्रैक्शनल नैप्सक के कांसेप्ट की बात करें तो ये चीज तो हमें पता है कि यहां पर हम ऑब्जेक्ट का पार्ट ले सकते हैं। ठीक है?सो तुम्हें ऐसे ऑब्जेक्ट सेलेक्ट करने हैं कि जो टोटल प्रॉफिट हो वो मैक्सिमम हो। लेकिन अगर सपोज बैग की कैपेसिटी 15 kg है तो वो उससे एक्सीड नहीं होना चाहिए। बस इतना कंस्ट्रेंट है। अब क्वेश्चन ये आता हैकि सबसे पहले कौन सा ऑब्जेक्ट उठाएंगे?है ना?तो इसके लिए तीन चॉइससेस हो सकती हैं कि भाई जिसका मैक्सिमम प्रॉफिट हो या फिर जिस ऑब्जेक्ट का वेट मिनिमम हो या फिर ऐसा ऑब्जेक्ट जिसका प्रॉफिट मैक्सिमम हो पर यूनिट वेट। ओके?
पर यूनिट वेट की बात कर रही हूं। यानी कि मैक्सिमम प्रॉफिट पर यूनिट वेट हो। तो फ्रैक्शनल नैप्सक के अंदर जो करेक्ट ग्रीडी चॉइस है वो है मैक्सिमम प्रॉफिट पर यूनिट वेट। ओके?तो यहां पर आप इसको समझ रहे हो। इसका जो फार्मूला है ये बहुत सिंपल है। देख लो जो रेश्यो आपको नजर आ रहा है। दैट इज P ऑफ़ आई/ w ऑफ़ आई दैट इज मैक्स प्रॉफिट पर यूनिट वेट।बस ये सिंपल सा इसका फार्मूला है। मतलब प्रॉफिट को वेट से डिवाइड करो। जिसका रेश्यो सबसे ज्यादा उसको पहले सेलेक्ट करो। बस यही पूरे टॉपिक की सबसे इंपॉर्टेंट ट्रिक है। ओके?अब अगर हम एल्गोरिदम की बात करें तो एल्गोरिदम को एकदम सिंपल लैंग्वेज में समझने की ट्राई करो। अगर आपको ऐसे कोड में नहीं लिखना है ना तो आप एल्गोरिदम को एकदम सिंपल इंग्लिश लैंग्वेज में भी लिख सकते हो।जैसे मैं आपको समझा रही हूं। स्टेप वन आपको क्या करना है?
देखो सभी ऑब्जेक्ट्स का प्रॉफिट टू वेट रेश्यो कैलकुलेट करना है। स्टेप टू आपको ऑब्जेक्ट्स को डिक्रीजिंग ऑर्डर में सॉर्ट करना है। मतलब कि जो हाईएस्ट रेश्यो होगा वो पहले आप लिखोगे। स्टेप थ्री आपके बैग में पूरा ऑब्जेक्ट फिटहो रहा है या नहीं हो रहा है वो आपको चेक करना है। ठीक है?अगर पूरा ऑब्जेक्ट फिट हो रहा है तो पूरा ऑब्जेक्ट ले लो। स्टेप फोर अगर पूरा ऑब्जेक्ट फिट नहीं हो रहा है तो जितनी कैपेसिटी बची है उतना फ्रैक्शन ले लो। क्लियर?और स्टेप फाइव बैग फुल होते ही स्टॉप कर दो। इसकी टाइम कॉम्प्लेक्सिटी आती है बिग ओ ऑफ़ n लॉग n क्योंकि सॉर्टिंग में बिग ऑफ़ n लॉग n टाइम लगता है। क्लियर?आई होप दिस इज़ वेरी वेरी क्लियर। ओके?नाउ लेट अस कम ऑन टू द पीवाईक्यू। अभी ये नवंबर दिसंबर का है। इसे बताने से पहले आई विल एक्सप्लेन यू मे जून 2024 का। ठीक है?
ये फ्रैक्शनल नैप्सक का क्वेश्चन आया था मई जून 2024 के अंदर कि फाइंड एन ऑप्टिमल सॉल्यूशन फॉर द नैप्सक इंस्टेंस यूजिंग ग्रीडी मेथड जिसमें n की वैल्यू आपको फाइव गिवन है m की वैल्यू 100 है ऑब्जेक्ट्स वेट कॉमाप्रॉफिट के अंदर करके दिए हुए हैं ऑब्जेक्ट्स आपके पास है 0 1 02 03 04 05 ठीक है अब यहां पर आपको क्या करना होगा सबसे पहला स्टेप सबसे पहला स्टेप आपको सबसे पहले हर ऑब्जेक्ट का प्रॉफिट डिवाइडबाय वेट करना पड़ेगा। है ना?आपके पास ऑब्जेक्ट कौन से हैं?देख लो। मैंने टेबल बनाई है। ऑब्जेक्ट है आपके पास 0 1 02 03 04 05। ओके?अब आपके पास आ जाता है वेट एंड प्रॉफिट। ठीक है?तो उनका वेट और प्रॉफिट दोनों भी क्वेश्चन के अंदर गिवन है। अब आपको क्या करना है?स्टेप वन में रेश्यो कैलकुलेट करना है। पर हमेशा याद रखना आपका जो रेश्यो होगा वो प्रॉफिट डिवाइड बाय वेट होगा। इसको बिल्कुल भी वेट डिवाइड बाय प्रॉफिट मत कर देना। ठीक है?
चलो प्रॉफिट डिवाइड बाय वेट करके आप हर ऑब्जेक्ट का रेश्यो फाइंड आउट कर लोगे। तो देखो फर्स्ट का हमारे पास आया 0.5 सेकंड का हमारे पास आया 0.67 थर्ड का हमारे पास आया 0.45 फोर्थ का हमारे पास आयावन और फाइव का हमारे पास आया 0.83 है ना?अब रेशोज़ को डिक्रीजिंग ऑर्डर में अरेंज करो। तो सबसे पहले क्या आएगा?04 फिर 05 फिर 02 फिर 0 1 और लास्ट में 03 क्लियर तो ये सॉर्टेड ऑर्डर में आपने क्या कर लिया अपने ऑब्जेक्ट्स को अरेंज कर लिया अब आ जाओ अब बैग की कैपेसिटी आपको कितनी गिवन है mदिया है आपको 100 kg ओके तो सबसे पहले आप क्या लोगे 04 लोगे यस इसका वेट 40 kg है और प्रॉफिट क्या है 40 है अब रिमेनिंग कैपेसिटी कितनी बची 100 - 40 कितनी बची 60 kg अब आपसेकंड लोगे क्या लोगे?05 है ना?
05 लेने के बाद इसका वेट क्या है?60 kg और प्रॉफिट क्या है?50 तो रिमेनिंग कैपेसिटी आपकी कितनी बची बताओ?60 - 60 दैट इज ज़ीरो। ओके?तो बैग कंप्लीटली फुल हो गया। तो यहां पर मुझे बताओ टोटल वेट 100 kg था और टोटल प्रॉफिट 40 + 50 यानी 90 हो गया। तो इस क्वेश्चन में किसी ऑब्जेक्ट का फ्रैक्शन लेने की जरूरत नहीं पड़ी। हैना?बहुत ज्यादा सिंपल। तो यहां पर आपको ऐसे लिख के दिखाना है। एंड बहुत ज्यादा सिंपल लैंग्वेज में आपका पूरा क्वेश्चन यहां पे सॉल्व हो गया। आप सिर्फ कैसे लिख के दिखाओगे?इसको सॉल्यूशन वेक्टर के अंदर आप इसको लिख के दिखा सकते हो कि भाई देखो ऐसे सॉल्यूशन वेक्टर के अंदर आप लिख के दिखा सकते हो कि आपने सिर्फ और सिर्फ x4 और x5 यानी कि 04 और 05 हीसेलेक्ट किया। बाकी ऑब्जेक्ट सेलेक्ट नहीं किए। ठीक है?
आपके पास वेट था 100 kg और मैक्सिमम प्रॉफिट आ गया 90। दैट्स इट। दैट्स इट। इतना ज्यादा सिंपल से आपको ये क्वेश्चन जो है स्यूशन इसका लिखना है पेपर के अंदर। ठीक है?
6. Fractional Knapsack PYQ November 2024
Solves the November-December 2024 fractional knapsack numerical with capacity 15, including fraction calculation and solution vector, with a note on 0/1 knapsack differences.
सो आई होप दिस थिंग इज वेरी क्लियर। अब हम ऊपर वाले क्वेश्चन में जाते हैं। ठीक है?ये था आपका नवंबर दिसंबर 2024 का क्वेश्चन। ओके?इसके अंदर भी देखो अब सेम चीज़ है। अब आप बहुत अच्छे से कर पाओगे। नैप्सक की कैपेसिटी आपको दी है 15। ओके?ऑब्जेक्ट्स यानी कि वेट कॉमा वैल्यू कर दिया है एंड आपको चार ऑब्जेक्ट्स दे दिए हैं। अब आपको यूज़ करना है ग्रीडी अप्रोच टू मैक्सिमाइज द टोटल वैल्यू विदाउट एक्सीडिंग द कैपेसिटी है ना?तो स्टेप वन आप क्या करोगे?स्टेप वन आप फाइंड आउट करोगे रेशो है ना?हर ऑब्जेक्ट का प्रॉफिट डिवाइड बाय वेट चेक करेंगे। ओके?तो प्रॉफिट डिवाइड बाय वेट आप करोगे। तो देख लो आपको कॉलम में दिख रहा है 0 1 0 2 03 04 ऑब्जेक्ट के लिए क्या-क्या रेश्यो आया हुआ है। ठीक है?फिर हमने क्या कर दिया?रैंक असाइन कर दी। रैंक असाइन करना यानी कि डिसेंडिंग ऑर्डर में हमने उनको सॉर्ट कर दिया। अब स्टेप टू हमें क्या करना है?
बैग के अंदर फिल करना है। ठीक है?तो बैग के अंदर फिल करने के लिए सबसे पहले आप कौन सा लोगे?04 लोगे। अब कैपेसिटी है 15 kg। राइट?तो सबसे पहले आप 04 लोगे जिसका वेट है 2 kg और प्रॉफिट है फोर। तो रिमेनिंग कैपेसिटी कितनी बची?15 - 2 13 kg बची। क्लियर?अब 02 वाला ऑब्जेक्ट लेंगे जिसका वेट है 4 kg और प्रॉफिट है एट ओके तो रिमेनिंग कैपेसिटी बची 13 - 6 7 kg ओके फिर आपके पास आता है 0 वन ऑब्जेक्ट जिसका टोटल वेट है 8 kg लेकिनलेकिन देखो हमारे पास क्या बचा है सिर्फ 7 kg कैपेसिटी बची है तो यहां पर हम पूरा ऑब्जेक्ट नहीं लेंगे तो क्या लेंगे भाई हम 7 / 8 7 / 8 फ्रैक्शन लेंगे ठीक है ये फार्मूला याद रखना।फ्रैक्शन का जो प्रॉफिट है वो आपको कैलकुलेट करना पड़ता है। फ्रैक्शन का प्रॉफिट क्या होता है हमेशा?
टोटल प्रॉफिट * टेकन वेट अप टोटल वेट। ओके?तो आपको बहुत अच्छे से समझ में आ गया होगा यहां पर 10 * 7/8 व्हिच इज इक्वल टू 8.75 कैसे आया है। क्लियर है?सो आई होप दिस थिंग इज वेरी क्लियर नाउ। एंड आप इसको ऐसे लिख के दिखा सकते हो कि कितना आपका जो सॉल्यूशन वेक्टर है उसमें आपने कौन सा ऑब्जेक्ट कितने प्रपोर्शन में लिया है। टोटल वेट कितना था बैगका एंड देन आपके पास मैक्सिमम वैल्यू क्या आई है?क्लियर?तो याद रखो गाइस दिस इज वेरी सिंपल। एंड ये वाले न्यूमेरिकल्स बिल्कुल भी मत छोड़ना। काफी ज्यादा स्कोरिंग आपके न्यूमेरिकल्स हो सकते हैं। ठीक है?अगेन फ्रैक्शनल नैप्सक और 0 वन नैप्सक को कंफ्यूज मत करना। अगर क्वेश्चन में 0 वन नैप्सक दिया है तो ग्रीडी रेशियो से हमेशा ऑप्टिमल आंसर नहीं मिलता। याद रखो। फॉर एग्जांपल इसी क्वेश्चन में अगर 0 वन नैप्सक के
लिए 01 और 02 सेलेक्ट करने पर वेट 14 kg और प्रॉफिट 18 मिलता है तो ये फ्रैक्शनल सॉल्यूशन के 20.75 से अलग है। ठीक है?तो आई होप कि ये चीज तो आपको बहुत ज्यादा क्लियर हो गई है। अब आ जाते हैं हम अपने सेकंड पार्ट के ऊपर दैट इज जॉब सीक्वेंसिंग विद डेडलाइंस। ओके?
7. Job Sequencing Concept and Latest PYQ
Explains the job sequencing with deadlines algorithm using latest available slots, and solves the November-December 2025 PYQ with four jobs.
ये आपका नेक्स्ट टॉपिक है। सी सपोज़ तुम्हारे पास मल्टीपल जॉब्स हैं। ओके?हर जॉब को कंप्लीट करने में एग्जैक्टली वन यूनिट ऑफ़ टाइम लगता है। हर जॉब की एक डेडलाइन होती है और एक प्रॉफिट होता है। तो अगर जॉब डेडलाइन के अंदर कंप्लीट हो गई तो प्रॉफिट मिलेगा। और यहां परहमें जॉब्स को ऐसे अरेंज करना है कि टोटल प्रॉफिट जो है वो मैक्सिमम हो जाए। ठीक है?तो यहां पर आप ग्रीडी अप्रोच का यूज करते हो। देखो ये स्टेप्स हैं जो कि मैं आपको समझाने जा रही हूं। स्टेप वन सभी जॉब्स को प्रॉफिट के डिसेंडिंग ऑर्डर में सॉर्ट करना पड़ेगा। मतलब हाईएस्ट प्रॉफिट वाली जॉबसबसे पहले। ओके?स्टेप टू मैक्सिमम डेडलाइन फाइंड करनी है। तो यहां पर उतने ही टाइम स्लॉट्स बना दो। फॉर एग्जांपल मैक्सिमम डेडलाइन थ्री है तो स्लॉट्स होंगे वन टू और थ्री। स्टेप थ्री की बात करूं तो हाईएस्ट प्रॉफिट वाली जॉब उठाओ
और उसको डेडलाइन के अंदर अवेलेबल लेटेस्ट स्लॉट में प्लेस कर दो। क्लियर?स्टेप फोर की अगर मैं बात करूं तो अगर कोई स्लॉट अवेलेबल नहीं है तो जॉब रिजेक्ट कर दो। ठीक है?लास्ट स्टेप फाइव सभी जॉब्स चेक करने के बाद सिलेक्टेड जॉब्स का प्रॉफिट ऐड कर दो। ठीक है?अब लेटेस्ट स्लॉट हमें क्यों लेना है?हमेशा यह बात याद रखो। बहुत इंपॉर्टेंट क्वेश्चन है। जॉब को लेटेस्ट अवेलेबल स्लॉट में ही क्यों प्लेस करते हैं?क्योंकि अगर हम जॉब को लेट स्लॉट में रखते हैं तो अर्लियर स्लॉट्स उन जॉब्स के लिए फ्री रहते हैं जिनकी डेडलाइंस जल्दी हैं। बस ये लॉजिक याद रखना। ठीक है?सो सिंपल लैंग्वेज में वापस एक्सप्लेन करूं। तो आप जॉब्स को सॉर्ट करोगे बाय डिक्रीजिंग प्रॉफिट। सेकंड आप मैक्सिमम डेडलाइन फाइंड करोगे। थर्ड आप एम्प्टी टाइम स्लॉट्स क्रिएट करोगे। फोर्थ आप सेलेक्ट करोगे जॉब्स इन प्रॉफिट ऑर्डर। फिफ्थ आप प्लेस
करोगे ईच जॉब इन द लेटेस्ट अवेलेबल स्लॉट बिफोर इट्स डेडलाइन। अब ये आप एग्जांपल से समझोगे तो अभी के लिए थोड़ा सा इसको स्किप कर दो। सिक्स्थ रिजेक्ट करोगे आप जॉब को इफ नो स्लॉट इज़ अवेलेबल। सेवंथ आपऐड करोगे प्रॉफिट्स को ऑफ द सिलेक्टेड जॉब्स। ठीक है?तो जो बेसिक एल्गोरिदम है यहां पर सॉर्टिंग का टाइम क्या लेगी?बिगो ऑफ़ n लॉगिन। सिंपल। सो आई होप ये आपको बहुत अच्छे से समझ में आ गया है। ओके?नाउ यही सारी चीजें जो मैंने आपको अच्छे से समझा दी है। अब एकदम इसका भी जो है ना कंट्रोल एब्स्ट्रैक्शन आता है। तो कंट्रोल एब्स्ट्रैक्शन के अंदर भी वही चीज़ है जो मैंने अभी आपको एल्गोरिदम में समझाई है।ठीक है?तो आप उसी चीज़ को यहां पर कंसीडर कर सकते हो। आ जाते हैं। हम अपना पीवाईक्यू देखते हैं। तो नवंबर दिसंबर 2025 एकदम लेटेस्ट आपका यह पीवाईक्यू है। यहां पर क्वेश्चन आपको गिवन है। वी आर गिवन फोर जॉब्स।
जॉब के अंदर आपको डेडलाइन और प्रॉफिट दिया है। ए, बी, सी, डी आपको ये जॉब्स गिवन है। ठीक है?एव्री जॉब टेक्स अ सिंगल यूनिट ऑफ़ टाइम। मैक्सिमाइज द टोटल प्रॉफिट इफ ओनली वन जॉब कैन बी शेड्यूल्ड एट अ टाइम यूजिंग अ ग्रीडी स्ट्रेटजी। ठीक है?ये आपको क्वेश्चन गिवन है। बहुत सिंपल है। स्टेप वन आपको क्या करना है?देखो स्टेप वन यहां पर आपको प्रॉफिट के अकॉर्डिंग देख लो या ध्यान से सुनो। प्रॉफिट के अकॉर्डिंग यहां पर आपको सॉर्ट करना है। सबसे पहले जॉब्स को हाईएस्ट प्रोफाइल प्रॉफिट से लोएस्ट प्रॉफिट के ऑर्डर में अरेंज करना पड़ेगा।तो यहां पर देख लो मेरे पास ए का प्रॉफिट है 75, सी का प्रॉफिट है 50, बी का प्रॉफिट है 40, डी का प्रॉफिट है 35। तो 75 50 40 35 तो मैंने अपनी जॉब्स को अरेंज कर दियाइन ऑर्डर ए सी बी डी तो ये सॉर्टेड ऑर्डर हो गया। अब मैक्सिमम डेडलाइन कितनी है?
टू। ओके?तो हमारे पास सिर्फ दो टाइम स्लॉट्स हैं। ओके?तो स्लॉट वन है आपके पास और स्लॉट टू है आपके पास। तो अभी फिलहाल स्लॉट वन और स्लॉट टू दोनों भी क्या है?एम्प्टी है। ठीक है?अब स्टेप टू पर आ जाते हैं जिसमें हम सबसे पहला जो है हमारी जॉब वो सेलेक्ट करेंगे। तो आप जॉब ए सेलेक्ट करोगे। फिर जॉब ए का जो प्रॉफिट है वो सबसे ज्यादा है। दैट इज 75। इसकी डेडलाइनटू है। मतलब स्लॉट वन या स्लॉट टू मुझे बताओ यहां पर आपको किस में प्लेस करना पड़ेगा?हमेशा लेटेस्ट स्लॉट में आपको प्लेस करना पड़ेगा। यानी कि स्लॉट टू के अंदर। ठीक है?स्लॉट टू के अंदर हम क्या करेंगे?लेटेस्ट अपने जॉब को प्लेस कर देंगे। तो हमारी स्लॉट वन अभी भी एम्प्टी है। स्लॉट टू के अंदर हमारे ए ऑब्जेक्ट है सॉरी ए जॉब है जिसके अंदर जिसका जो वैल्यू है वो है 75। ओके?
अब स्टेप्स आप अपने आ जाओ किसके पास?अब आपको सेकंड चूज़ करना है दैट इज जॉब सी। तो जॉब सी आप सेलेक्ट करोगे। अब जॉब सी का प्रॉफिट है 50 और इसकी डेडलाइन है वन। ठीक है?तो इसको हम स्लॉट वन में प्लेस कर देंगे क्योंकि डेडलाइन भी वन है। ओके?तो स्लॉट वन में आ गया सी विद 50 प्रॉफिट एंड स्लॉट टू में आ गया ए विद 75 प्रॉफिट। तो जॉब बी और जॉब डी को चेक करो। जॉब डी का प्रॉफिट 40 है और डेडलाइन वन है। लेकिनस्लॉट वन ऑलरेडी ऑक्यूपाइड है तो जॉब बी रिजेक्ट होगी। ठीक है?नेक्स्ट जॉब डी का प्रॉफिट 35 है और डेडलाइन टू है। स्लॉट टू और स्लॉट वन दोनों ऑक्यूपाइड हैं तो जॉब डी भी रिजेक्ट होगी। ओके?अब सिलेक्टेड जॉब्स हैं सी और ए। तो टोटल प्रॉफिट क्या हो गया गाइस?टोटल प्रॉफिट आपका हो गया 50 + 75 यानी मैक्सिमम प्रॉफिट हो गया 125। ठीक है?
तो फाइनल शेड्यूल आपका कैसे होगा?सी फिर ए। तो बेस्ट जॉब सीक्वेंसिंग में दो चीजें याद रखना। सबसे पहले जॉब्स का प्रॉफिट के डिसेंडिंग ऑर्डर में सॉर्ट करना पड़ेगा। ठीक है?देन हर जॉब को डेडलाइन से पहले लेटेस्ट अवेलेबल स्लॉट में प्रेस करना पड़ेगा। दैट्स इट। ओके। सो आई होप ये भी वाला जो पीवाईक्यू है, ये आपको बहुत अच्छे से समझ में आ गया है। ओके?
8. Job Sequencing PYQ with Feasible Solutions
Solves the November-December 2023 job sequencing question with five jobs, finding feasible solutions, optimal solution, and maximum profit of 40.
यहां पर देख लो। ये भी आपका नवंबर दिसंबर 2023 का क्वेश्चन है। क्या क्वेश्चन है?देखो। राइट अ हाई लेवल डिस्क्रिप्शन ऑफ़ द जॉब सीक्वेंसिंग एल्गोरिदम। n = 5 प्रॉफिट p = 20 15 10 5 1 डेडलाइन d = 2 1 33 फाइंड द फिजिबल सॉलशंस। व्हाट इज द ऑप्टिमल सॉल्यूशन एंड मैक्सिमम प्रॉफिट?ठीक है?स्टेप वन हम सबसे पहले भाई अंडरस्टैंड कर लेते हैं। क्या है क्वेश्चन?सबसे पहले यहां पर इस क्वेश्चन में फाइव जॉब्स आपको गिवन है। ठीक है?J1, J2, J3, J4, J5। हर जॉब का प्रॉफिट और डेडलाइन गिवन है। है ना?सिंपल लैंग्वेज में?चलो, अब इसका हमने टेबल बना लिया ईजी टू अंडरस्टैंड। सबसे पहले मैक्सिमम डेडलाइन देखो। तो, मैक्सिमम डेडलाइन क्या है?थ्री है तो हमारे पास थ्री टाइम स्लॉट्स होंगे। ओके?अब थ्री टाइम स्लॉट्स होंगे। यह हमें समझ में आ गया। क्यों?क्यों भाई?क्योंकि मैक्सिमम डेडलाइन थ्री है। ओके?
चलो स्टेप वन हमारा पूरा हो जाता है। स्टेप टू हमें क्या करना पड़ेगा?हमारी जॉब्स को सॉर्टेड कर सॉर्टिंग ऑर्डर के अंदर अरेंज करना पड़ेगा। अब यहां पर आपको कैसे करना पड़ेगा?सॉर्ट जॉब्स को बाय प्रॉफिट। तो जो हाईएस्ट प्रॉफिट है वो आपको सबसे पहले रखना है और फिर लोएस्ट प्रॉफिट तक अपने जॉब्स को अरेंज करना है। तो जो ऑर्डर है वो कैसा होगा?J1, J2, J3, J4। अब हर जॉब को उसके डेडलाइन के अंदर लेटेस्ट अवेलेबल स्लॉट में प्लेस करेंगे। तो यहां पर हमें अपने स्लॉट्स फिल करने हैं। तो देखो J1 का प्रॉफिट क्या है?20 है। और डेडलाइन क्या है?टू है। तो इसको स्लॉट टू में प्लेस करेंगे। अब J2 का प्रॉफिट 15 है और डेडलाइन टू है। तो स्लॉट टू तो ऑक्यूपाइड है लेकिन स्लॉट वन अवेलेबल है। तो J2 को हम स्लॉट वन में प्लेस करेंगे। ठीकहै?J3 की डेडलाइन वन है लेकिन स्लॉट वन ऑलरेडी ऑक्यूपाइड है तो उसको रिजेक्ट कर दो। J4 की डेडलाइन थ्री है। स्लॉट थ्री अवेलेबल है तो J4 को स्लॉट थ्री में प्लेस करेंगे। ओके?
J5 की डेडलाइन थ्री है लेकिन तीनों स्लॉट्स फुल है तो J5 को रिजेक्ट कर दो। क्लियर हो गया?तो स्लॉट वन के अंदर देखो एकदम सिंपल लैंग्वेज में समझ में आ रहा है आपको?स्लॉट वन के अंदर अगर हम देखें तो J2 है जिसका प्रॉफिट है 15। ठीक है?देन स्लॉट टू के अंदर J1 है जिसका प्रॉफिट है 20। और स्लॉट थ्री के अंदर J4 है जिसका प्रॉफिट है फाइव। ओके?अब हमें मैक्सिमम प्रॉफिट कैलकुलेट करना है। तो जो सिलेक्टेड जॉब्स हैं उनका प्रॉफिट आप ऐड कर दोगे। 15 + 20 + 5 आप ऐड कर दो। आपको मिल जाएगा 40। ठीक है?तो फाइनल आंसर ऑप्टिमल जॉब सेट क्या है?J1, J2 एंड J4। और इनका मैक्सिमम प्रॉफिट क्या है?40 है। ठीक है?अब यहां पर आपको ये बहुत अच्छे से समझ में आ गया होगा। यही चीज मैंने आपको एक्सप्लेन की है। ठीक है?
यही जॉब, एक्शन सारी चीजें मैंने आपको बहुत अच्छे से एक्सप्लेन कर दी हैं। ठीक है?अब फिजिबल सॉल्यूशन क्या होता है?तो क्वेश्चन में फिजिबल सॉल्यूशन भी पूछे हैं। राइट?तो फिजिबल सॉल्यूशन मतलब ऐसा जॉब सिलेक्शन जिसमें हर जॉब अपनी डेडलाइन के अंदर कंप्लीट हो सके। फॉर एग्जांपल J1 और J2 दोनों सिलेलेक्ट कर सकते हैं। क्योंकि दोनों की डेडलाइन टू है और हम उन्हें दो अलग स्लॉट्स मेंकंप्लीट कर सकते हैं। है ना?लेकिन J1, J2 और J3 तीनों को एक साथ सेलेक्ट नहीं कर सकते। इन तीनों की डेडलाइंस टू या उससे कम है। लेकिन इन्हें कंप्लीट करने के लिए सिर्फ दो स्लॉट्स अवेलेबल है। इसलिए ये सिलेक्शन इनफिजिबल है जो मैंनेऊपर लिखा हुआ है यहां पे। ठीक है?इनफिजिबल है। क्लियर?सो रिमेंबर फिजिबल मींस जॉब्स कैन फिनिश विद इन देयर डेडलाइंस। ओके?
9. More Job Sequencing PYQs
Solves additional job sequencing questions from November-December 2023 and May-June 2023 with multiple examples, and summarizes the key steps of the algorithm.
सो आई होप ये वाली चीज आपको बहुत अच्छे से समझ में आ गई है। अब यहां पर देख लो ये भी एक क्वेश्चन है नवंबर दिसंबर 2023 में कि व्हाट इज द जॉब शेड्यूलिंग एल्गोरिदम?हाउ कैन इट बी सॉल्वड यूजिंग गीडी अप्रोच एक्सप्लेन विद रिस्पेक्ट टू प्रिंसिपल कंट्रोल एब्स्ट्रैक्शन एंड टाइम एनालिसिस ऑफ़ कंट्रोल एब्स्ट्रैक्शन फॉर द फॉलोविंग इंस्टेंस। ओके?यहां पर जॉब्स J1 टू J 5 गिवन है। डेडलाइन 2 1 3 2 1 गिवन है। प्रॉफिट आपको 60 100 20 40 और 20 गिवन है। ठीक है?तो इसको आप कैसे सॉल्व करोगे?देख लो। आप बहुत ज्यादा सिंपल वे में इसको सॉल्व कर सकते हो यूजिंग द बेसिक थिंग्स। है ना?यहां पर आपने जो ये सारी चीजें दी है। पहले आप डिक्रीजिंग ऑर्डर के अंदर इन द फॉर्म ऑफ प्रॉफिट आप अरेंज करोगे। है ना?ओके। चलो यहां पर मैं वो ही एक्सप्लेन किया हुआ है। यहां पर जॉब्स हैं J2, J1, J4, J3, J5। ठीक है?
इस फॉर्मेट में हमने सॉर्टेड ऑर्डर के अंदर अरेंज कर लिया है। अब मैक्सिमम डेडलाइन थ्री है। सो टोटल थ्री स्लॉट्स होंगे। अब आपको स्लॉट्स फिल करने हैं। तो J2 का प्रॉफिट 100 है और डेडलाइन वन है तो स्लॉटवन में आप इसको प्लेस कर दोगे। J1 का प्रॉफिट 60 है और डेडलाइन टू है। तो लेटेस्ट अवेलेबल स्लॉट इज़ स्लॉट टू। तो वहां प्लेस करोगे। ओके?J4 का प्रॉफिट 40 है और डेडलाइन टू है। स्लॉट टू और स्लॉट वन दोनों ऑक्यूुपाइड है तो आप रिजेक्ट कर दोगे। J3 का प्रॉफिट 20 है और डेडलाइन थ्री है। स्लॉट थ्री अवेलेबल है तो वहां प्लेस कर दोगे।J5 की डेडलाइन वन है लेकिन स्लॉट वन ऑक्यूपाइड है। सो रिजेक्ट कर दोगे। ठीक है?तो आपके टाइम स्लॉट्स कैसे डिवाइड हो गए?देख लो। स्लॉट वन में आपके पास J2 है विद प्रॉफिट 100। स्लॉट टू के अंदर J1 है विद प्रॉफिट 60 एंड स्लॉट थ्री के अंदर J3 है विद प्रॉफिट 20 क्लियर तो फाइनल फाइनल सीक्वेंस आपकी क्या आ गई
J2 J1 J3 और मैक्सिमम प्रॉफिट आपके पास आ गया 180 क्लियर है बहुत ज्यादा सिंपल सा था ये ओके ये वाला क्वेश्चन देख लो मेई जून 2023 के अंदर पूछा गया है इस क्वेश्चन में दो एग्जांपल्स दिए हैंदेखो दोनों को सेम एल्गोरिदम से सॉल्व करना है सबसे पहले व्हाट इज द ग्रीडी अप्रोच एक्सप्लेन जॉब जॉब शेड्यूलिंग एल्गोरिदम यूजिंग ग्रीडी अप्रोच फॉर फॉलोइंग एग्जांपल एंड गिव द सीक्वेंस ऑफ़ जॉब शेड्यूलिंग। यहां पर आपको ए बी सीडी जॉब्स गिवन है और एग्जांपल टू के अंदर भी ए बी सी डी जॉब्स गिवन है। जी डी के साथ ई भी है जॉब एग्जांपल टू में। चलो समझ में आ रहा है?यहां पर ये दोनों एग्जांपल्स को हमें जॉब शेड्यूलिंग एल्गोरिदम के थ्रू सॉल्व करना है। चलो एग्जांपल वन की अगर हम बात करें। एग्जांपल वन के अंदर हम देखें तो सबसे पहले सॉर्टेड ऑर्डर के अंदर अरेंज करेंगे। तो जॉब्स
हमारी फॉर्मेट के अंदर है डेडलाइन कॉमा प्रॉफिट। ठीक है?तो यहां पर आपके पास ए, बी, सी, डी करके जॉब्स हैं। सॉर्ट करेंगे बाय प्रॉफिट। तो हमारे पास जो सॉर्टिंग आएगी वो आएगी सी, डी, ए, बी। ठीक है?ये सॉर्टेड ऑर्डर आ जाएगा। मैक्सिमम डेडलाइन फोर है तो फोर स्लॉट्स होंगे। अब हमें क्या करना है?जॉब्स को शेड्यूल करना है। है ना?तो जॉब सी का प्रॉफिट अगर आप देखो वो है 40 और डेडलाइन है वन। तो स्लॉट वन में आप प्लेस कर दोगे। जॉब डी की डेडलाइन वन है लेकिन स्लॉट वन ऑक्यूपाइड है तो रिजेक्ट कर दोगे। जॉब एकी डेडलाइन फोर है। स्लॉट फोर अवेलेबल है तो स्लॉट फोर में प्लेस कर दोगे। ठीक है?अब जॉब बी की जो डेडलाइन है वो वन है लेकिन स्लॉट वन ऑक्यूपाइड है तो रिजेक्ट कर दोगे। क्लियर?तो हमारे पास स्लॉट वन, स्लॉट टू, स्लॉट थ्री एंड स्लॉट फोर के अंदर देखो कैसे आएंगी चीजें। यहां पर स्लॉट वन में आपके पास सी आ जाएगा विद प्रॉफिट 40। स्लॉट टू इज़ एम्प्टी, स्लॉट थ्री इज़ एम्प्टी एंड
स्लॉट फोर के अंदर आपके पास ए आ जाएगा विद प्रॉफिट 20। ठीक है?आई होप दिस थिंग इज क्लियर। तो फाइनल सीक्वेंस आएगी C फॉललोड बाय A एंड प्रॉफिट जो है आपका मैक्सिमम प्रॉफिट वो आएगा 60। ठीक है?अब एग्जांपल टू की बात करें तो अगेन इसको सॉर्टेड ऑर्डर में अरेंज करेंगे तो हमें मिलेगा ए, सी, डी, बी, ई। ठीक है?अब मैक्सिमम डेडलाइन थ्री है तो थ्री स्लॉट्स होंगे। जॉब ए का प्रॉफिट 100 है। है ना?जॉब ए का प्रॉफिट 100 है और डेडलाइन टू। तो इसको स्लॉट टू में प्लेस करेंगे। जॉब सी का प्रॉफिट 27 है और डेडलाइन टू लेकिन स्लॉट टू तो ऑक्यूपाइड है। तो यहां पर हम इसको स्लॉट वन में चेककरेंगे जो कि अवेलेबल है। तो सी को स्लॉट वन में प्लेस कर देंगे। जॉब डी की डेडलाइन वन है लेकिन स्लॉट वन ऑक्यूपाइड है तो रिजेक्ट कर देंगे। जॉब बी की डेडलाइन वन है। स्लॉट वन अभी भी ऑक्यूपाइड
है तो रिजेक्ट कर देंगे। जॉब ई की डेडलाइन थ्री है। स्लॉट थ्री अवेलेबल है तो ई को स्लॉट थ्री में प्लेस कर देंगे। तो हमारे पास स्लॉट वन स्लॉट टू स्लॉट थ्री के अंदर देखो कैसे आ गया। स्लॉटवन में आपके पास सी आ गया विद प्रॉफिट 27। स्लॉट टू के अंदर ए आ गया विद प्रॉफिट 100 एंड स्लॉट थ्री के अंदर ई आ गया विद प्रॉफिट 15। ओके?तो आप मैक्सिमम प्रॉफिट कैलकुलेट करोगे। सीक्वेंस आपकी होगी सीएई और मैक्सिमम प्रॉफिट होगा 142। ओके?तो गाइस जॉब सीक्वेंसिंग के सारे न्यूमेरिकल सॉल्व कर लिए हमने। बहुत ज्यादा अच्छे से हमने समझ लिया। क्या करना है देख लो आपको?तो जॉब्स को डिक्रीजिंग प्रॉफिट में सॉर्ट करना है। मैक्सिमम डेडलाइन चेक करनी है। उतने टाइम स्लॉट्स बनाने हैं। हर जॉब को डेडलाइन के अंदर लेटेस्ट अवेलेबल स्लॉट में प्लेस करना है। सिलेक्टेड जॉब्स के प्रॉफिट को ऐड करना है।
अगर स्लॉट अवेलेबल नहीं है तो जॉब रिजेक्ट कर दो। प्रॉफिट डिसेंडिंग, लेटेस्ट स्लॉट, मैक्सिमम प्रॉफिट। ये तीन चीजें याद रखो। तो जॉब सीक्वेंसिंग के न्यूमेरिकल्स बहुत इजीली सॉल्व हो जाएंगे। ठीक है?
10. Task Scheduling to Minimize Penalty
Explains the highest penalty first greedy strategy for task scheduling, its algorithm and complexity, then solves the previous year question with seven tasks and proves correctness.
आई होप दिस थिंग इज़ वेरी क्लियर। नाउ लेट अस सी शेड्यूलिंग टास्क टू मिनिमाइज पेनल्टी। ओके?तो सपोज देखो ये बहुत इजी है। सपोज़ तुम्हारे पास मल्टीपल टास्क हैं। हर टास्क की एक डेडलाइन है। और अगर टास्क डेडलाइन तक कंप्लीट नहीं हुआ तो पेनल्टी देनी पड़ेगी। ठीक है?अब हमें टोटल पेनल्टी मिनिमम करनी है। तो ऑब्वियस है जिस टास्क की पेनल्टी सबसे ज्यादा है उसको टाइम पर कंप्लीट करने की कोशिश करेंगे। ठीक है?तो यहां पर ग्रेडी रूल आपको यूज़ करना पड़ेगा। कौन सा?हाईएस्ट पेनल्टी फर्स्ट। लेकिन एक इंपॉर्टेंट बात सिर्फ पेनल्टी के डिक्रीजिंग ऑर्डर में टास्क अरेंज करना इनफ नहीं है। हर टास्क को उसकी डेडलाइन के अंदर किसी अवेलेबल टाइम स्लॉट में प्लेस करना भी जरूरी है। ओके?तो चलो इसके एल्गोरिदम एकदम सिंपल लैंग्वेज में मैं आपको समझा देती हूं जो कि क्वेश्चन भी है। ओके?देखो एल्गोरिदम अगर मैं आपको एकदम सिंपल लैंग्वेज में समझाऊं तो सबसे पहला स्टेप आप टास्क को डिक्रीजिंग ऑर्डर ऑफ़ पेनल्टी में सॉर्ट करते हो। ठीक है?
स्टेप टू आप मैक्सिमम डेडलाइन के अकॉर्डिंग टाइम स्लॉट्स बनाते हो। ठीक है?स्टेप थ्री के अंदर हाईएस्ट पेनल्टी वाला जो टास्क है वो आप उठाते हो। स्टेप फोर उस टास्क को डेडलाइन के अंदर लेटेस्ट अवेलेबल स्लॉट में प्लेस करो। ठीक है?स्टेप फाइव अगर कोई स्लॉट अवेलेबल नहीं है तो टास्क लेट होगा और उसकी पेनल्टी पे करनी पड़ेगी। फाइनली जो लेट टास्क हैं उनकी पेनल्टी आपको ऐड कर देनी है। ठीक है?तो आपको कैसे करना है?सॉर्ट करना है। फ्री स्लॉट फाइंड आउट करना है। फिर शेड्यूल करना है। फिर पेनल्टी कैलकुलेट करनी है। ठीक है?अब टाइम कॉम्प्लेक्सिटी की अगर मैं बात करूं तो यहां पर सॉर्टिंग का टाइम बिग ओ ऑफ़ n लॉग n है। ठीक है?तो हर टास्क के लिए अवेलेबल स्लॉट सर्च करने में वर्स्ट केस बिग ओ ऑफ़ n टाइम लग सकता है। इसीलिए जो बेसिक एल्गोरिदम की टाइम कॉम्प्लेक्सिटी है वो है बिग ओ ऑफ़ n²। तो एग्जाम में एल्गोरिदम, ग्रीडी स्ट्रेटजी,
टाइम कॉम्प्लेक्सिटी और करेक्टनेस का एक्सप्लेनेशन लिखना इजेंट। ओके?नाउ लेट अस कम ऑन टू दिस पर्टिकुलर पीवाईक्यू। ठीक है?इस पीवाईक्यू में क्या लिखा है?लेट अस अंडरस्टैंड। ये क्वेश्चन है। आपको एग्जांपल अस्यूम करके जो है एक्सप्लेन करने बोला था। तो लेट अस्यूम दिस थिंग। पहले मैं आपको एक ये पीवाईक्यू पढ़ के समझा देती हूं। क्या है क्वेश्चन में?यू आर गिवन अ सेट ऑफ़ टास्क ईच विद अ डेडलाइन एंड अ पेनल्टी फॉर मिसिंग द डेडलाइन। ठीक है?द ऑब्जेक्टिव इज़ टु शेड्यूल दीज़ टास्क इन अ वे दैट मिनिमाइज़ज़ द टोटल पेनल्टी इंकर्ड। यू कैन वर्क ऑन ओनली वन टास्क ऐट अ टाइम। एंड वंस अ टास्क इज़ स्टार्टेड, इट मस्ट बी कंप्लीटेड बिफोर मूविंग टू दनेक्स्ट टास्क। ओके?यू कांट स्टार्ट अ टास्क आफ्टर इट्स डेडलाइन हैज़ पास्ड। सो यू हैव टू डिजाइन अ ग्रीडी एल्गोरिदम टू एफिशिएंटली शेड्यूल दी टास्क टू मिनिमाइज द टोटल पेनल्टी एंड प्रूव इट्स करेक्टनेस। क्लियर है?
तो चलो अब यहां पर आपको अस्यूम क्या करना है?ईच टास्क टेक्स वन यूनिट ऑफ़ टाइम। टास्क आई हैज़ डेडलाइन डीआई एंड पेनल्टी Wi। ठीक है?चलो ये एल्गोरिदम लिखो या मत लिखो। यहां पर एग्जांपल के थ्रू हमें उन्हें एक्सप्लेन करना है। है ना?तो यहां पर इस एग्जांपल को समझते हैं। सी हमारे पास सेवन टास्क हैं। हर टास्क के अंदर यहां पर हर टास्क को 1 यूनिट ऑफ टाइम लगता है। क्लियर?तो टास्क आपके पास 1 2 3 4 5 6 7 है। डेडलाइन है 4 2 4 3 1 4 6 पेनल्टी है 70 60 50 40 30 20 एंड 10 क्लियर। नाउ यह टास्क ऑलरेडी पेनल्टी के डिसेंडिंग आर्डरमें है। अब हर टास्क को डेडलाइन के अंदर लेटेस्ट अवेलेबल स्लॉट में प्लेस करना है। क्लियर?तो यहां पर सबसे पहले आप क्या करोगे?टास्क शेड्यूल करोगे। है ना?टास्क शेड्यूल करना है। यानी कि टास्क वन की डेडलाइन क्या है?
याद करो। टास्क वन की यहां पर डेडलाइन क्या है?इज इट हियर?चलो आई एम एक्सप्लेनिंग। टास्क वन की डेडलाइन फोर है। स्लॉट फोर में प्लेस कर दो। टास्क टू की डेडलाइन टू है। स्लॉट टू में प्लेस कर दो। टास्क थ्री की डेडलाइन फोर है। स्लॉट फोर ऑक्यूपाइड है। तो स्लॉटथ्री अवेलेबल है ना?तो स्लॉट थ्री में प्लेस कर दो। टास्क फोर की डेडलाइन थ्री है। स्लॉट थ्री और टू ऑक्यूपाइड है लेकिन स्लॉट वन अवेलेबल है। तो स्लॉट वन में प्लेस कर दो। टास्क फाइव की डेडलाइन वन है। लेकिन स्लॉट वनऑक्यूपाइड है। यह टास्क लेट होगा। टास्क सिक्स की डेडलाइन फोर है। स्लॉट्स वन से फोर तक सब फुल है। ये भी लेट हो जाएगा। टास्क सेवन की डेडलाइन सिक्स है। स्लॉट सिक्स अवेलेबल है तो स्लॉट सिक्स में प्लेसकर दो। अब यहां पर अगर आप स्लॉट्स देखो तो आपके फर्स्ट स्लॉट के अंदर टास्क फोर है। सेकंड स्लॉट में टास्क टू है। थर्ड स्लॉट में टास्क थ्री है। फोर्थ टाइम स्लॉट में आपके पास टास्क वन है। फिफ्थ
स्लॉट एंप्टी है। सिक्स्थ स्लॉट में आपके पास टास्क सेवन है। तो लेट टास्क कौन से हो गए?लेट टास्क आपके पास हो गए टास्क फाइव एंड टास्क सिक्स। ठीक है?अब आपको इनकी टोटल पेनल्टी कैलकुलेट करनी पड़ेगी। अब सिर्फ लेट टास्क की पेनल्टी आप ऐड करोगे। टास्क फाइव की पेनल्टी 30 है और टास्क सिक्स की पेनल्टी 20 है। तो कुछ नहीं आपको 30 + 20 कर देना है।तो मैक्सिमम सॉरी मिनिमम टोटल पेनल्टी आपके पास आ गई 50। क्लियर?अब इसके प्रूफ ऑफ करेक्टनेस आपको यहां पर देना पड़ता है। अब क्वेश्चन में प्रूफ ऑफ करेक्टनेस भी पूछा है। तो इसको एकदम सिंपल लैंग्वेज में समझते हैं। फर्स्ट हाईएस्ट पेनल्टी फर्स्ट। क्या?हाईएस्ट पेनल्टी फर्स्ट। अगर किसी हायर पेनल्टी टास्क को लेट कर रहे हैं जबकि उसकी जगह लोअर पेनल्टी टास्क को टाइम पर कंप्लीट किया जा सकता है तो दोनों को स्वाइप करने से पेनल्टी कम हो सकती है। इसीलिए हाई
पेनल्टी टास्क को प्रायोरिटी देना सेंसिबल है। क्लियर?सेकंड लेटेस्ट अवेलेबल स्लॉट। ठीक है?तो जो टास्क है टास्क को डेडलाइन के अंदर लेटेस्ट फ्री स्लॉट में प्लेस करने से अर्लियर स्लॉट्स उन टास्क के लिए फ्री रहते हैं जिनकी डेडलाइन जल्दी है। सिंपल। थर्ड मिनिमम पेनल्टी। मिनिमम पेनल्टी यानी टोटल पेनल्टी को मिनिमाइजकरना। टाइम पर कंप्लीट किए गए टास्क की टोटल पेनल्टी को मैक्सिमाइज करने के इक्विवेलेंट है। इसीलिए ग्रीडी स्ट्रेटजी हाईएस्ट पेनल्टी टास्क को प्रायोरिटी देती है और अवेलेबल स्लॉट्स को एफिशिएंटली यूज़ करती है। ओके?सो आई होप यू अंडरस्टुड दिस। दिस वाज़ वेरी वेरी सिंपल। नाउ लेट अस अंडरस्टैंड एक्टिविटी सिलेक्शन प्रॉब्लम। ओके?
11. Activity Selection Problem and PYQ
Covers the activity selection greedy approach of choosing earliest finishing activities, its algorithm and complexity, and solves the May-June 2025 question with seven activities.
अब ये जो है सपोज़ बहुत ज्यादा सिंपल है ये। सपोज़ तुम्हारे पास एक रूम है और मल्टीपल एक्टिविटीज है। हर एक्टिविटी का स्टार्ट टाइम और फिनिश टाइम दिया है। तो रूम में एक टाइम पर सिर्फ एक एक्टिविटी होसकती है। हमें मैक्सिमम नंबर ऑफ एक्टिविटी सेलेक्ट करनी है बिना किसी ओवरलैप के। तो क्वेश्चन है सबसे पहले कौन सी एक्टिविटी सेलेक्ट करेंगे?है ना?ग्रीडी रूल तो यही बोलता है कि सेलेक्ट करो वो एक्टिविटी जो मतलब सबसे पहले फिनिश हो जाए। है ना?क्योंकि जो एक्टिविटी जल्दी फिनिश होगी वो नेक्स्ट एक्टिविटीज के लिए ज्यादा टाइम फ्री कर देगी। है ना?अब इसकी एल्गोरिदम की अगर हम बात करें तो सिंपल लैंग्वेज के अंदर स्टेप वन एक्टिविटीज को इंक्रीजिंग ऑर्डर ऑफ फिनिश टाइम में सॉर्ट करो। स्टेप टू सबसे पहले फिनिश होने वाली एक्टिविटी सेलेक्ट करो। स्टेप थ्री अब नेक्स्ट एक्टिविटीचेक करो। अगर उसका स्टार्ट टाइम लास्ट सिलेक्टेड एक्टिविटी के फिनिश टाइम से ग्रेटर देन या फिर इक्वल है तो सेलेक्ट कर लो। अदरवाइज रिजेक्ट कर दो। स्टेप फोर सभी एक्टिविटीज चेक होने तक रिपीट करो। ओके?
सो आई थिंक ये चीज बहुत ज्यादा क्लियर हो गई है आपको। ओके?सो यहां पर अगर मैं आपको बताऊं अ सिंपल जो यहां पर लिखा हुआ है कि यहां पर एस ऑफ़ आई है दैट इज योर करंट एक्टिविटी जो कि स्टार्टिंग टाइम है और f ऑफ आई यानी कि आपके सिलेक्टेडएक्टिविटी का फिनिश टाइम। अगर कंडीशन ट्रू है। कौन सी वाली?एस ऑफ आई इज़ ग्रेटर दैन इक्वल टू एफ ऑफ लास्ट। है ना?तो अगर ये कंडीशन ट्रू है तो एक्टिविटी सेलेक्ट होगी। अदरवाइज रिजेक्ट हो जाएगी। क्लियर?टाइम कॉम्प्लेक्सिटी की बात करें तो अगर एक्टिविटीज को सॉर्ट करना है तो सॉर्टिंग कॉम्प्लेक्सिटी तो हमें पता ही है बिगो ऑफ़ n लॉग n होती है। उसके बाद एक सिंगल स्कैन में एक्टिविटीज चेक करेंगे जिसका टाइम बिगो ऑफ़n है। इसीलिए यहां पर बिगो ऑफ़ n लॉग n यहां पर लिखा हुआ है। अगर एक्टिविटीज पहले से फिनिश टाइम के अकॉर्डिंग सॉर्टेड है तो कॉम्प्लेक्सिटी बिगो ऑफ़ n होगी। क्लियर है?
अब यह पीवाईक्यू देख लो जो एक्टिविटी सिलेक्शन के ऊपर एकदम रीसेंट है। क्या?मे जून 2025 का है। क्या है क्वेश्चन?देखो। कंसीडर अ सेट ऑफ़ सेवन एक्टिविटीज़ विद स्टार्ट कॉमा फिनिश। ए, बी, सी, डी, ई, एफ, जी आपको गिवन है एक्टिविटीज़। यूज़ द ग्रीडी एल्गोरिथमिक स्ट्रेटजी टू कंप्यूट एन एग्जीक्यूशन शेड्यूल हैविंग द मैक्सिमम नंबर ऑफ़ नॉन कॉन्फ्लिक्टिंग एक्टिविटीज़।चलो, स्टेप वन है। सॉर्ट करो बाय फिनिश टाइम। है ना?सबसे पहले फिनिश टाइम के इंक्रीजिंग ऑर्डर में एक्टिविटीज अरेंज करेंगे। यहां एक्टिविटीज ऑलरेडी सॉर्टेड हैं। अगर आप ध्यान से देखो तो ए, बी, सी, डी, ई, एफ, जी। क्लियर?स्टेप टू सेलेक्ट करो फर्स्ट एक्टिविटी। ओके?सेलेक्ट कर लो फर्स्ट एक्टिविटी। अब एक्टिविटी ए का स्टार्ट टाइम वन है और फिनिश टाइम थ्री है। ये सबसे पहले फिनिश होती है। तो ए को सेलेक्ट कर लेंगे। अब लास्ट फिनिश टाइम क्या हो गया आपका?थ्री हो गया। अब आप एक्टिविटी बी चेक करोगे। एक्टिविटी बी का स्टार्ट टाइम थ्री है और ए का फिनिश टाइम भी थ्री है। तो कंडीशन चेक करो भाई। कंडीशन चेक हो गई। कंडीशन ट्रू है हमारी। तो बी सेलेक्ट
कर लेंगे। अब लास्ट फिनिश टाइम क्या हो गया?फोर हो गया। एक्टिविटी सी चेक करो। एक्टिविटी सी चेक करो। एक्टिविटी सी का स्टार्ट टाइम टू है। लेकिन लास्ट सिलेक्टेड एक्टिविटी बी का फिनिश टाइम फोर है। तो यहां पर आपकी कंडीशन फॉल्स हो जाती है। हम सी कोरिजेक्ट कर देंगे। ठीक है?अब आ जाओ। आप चेक करो एक्टिविटी डी। एक्टिविटी डी का स्टार्ट टाइम जीरो है। है ना?तो यह तो भाई सामने से फॉल्स है इसलिए डी भी रिजेक्ट हो गया। एक्टिविटी ई चेक करो। इसका स्टार्ट टाइम फाइव है और लास्ट फिनिश टाइम फोर है। तो यहां पर आपकी कंडीशन ट्रू हो गई। तो ई आपसेलेक्ट कर लेंगे। अब लास्ट फिनिश टाइम नाइन हो गया। है ना?अब एक्टिविटी फाइव को चेक करें। सॉरी एफ को चेक करें। तो एक्टिविटी एफ का स्टार्ट टाइम एट है। है ना?यहां पर भी कंडीशन फॉल्स हो गई। एफ रिजेक्ट हो जाएगा। एक्टिविटी जी को चेक करें। स्टार्ट टाइम 11 है और लास्ट फिनिश टाइम नाइन है। तो ये आपकी कंडीशन ट्रू कर रहा है। तो जी भी आप सेलेक्ट कर
लेंगे। ये टाइमलाइन देख लो। ऐसी आपको टाइमलाइन ड्रॉ करनी पड़ेगी। एंड बहुत इजी वे में आपका पूरा जो क्वेश्चन है वो यहां पे सॉल्व हो गया। आपको बस ये मैक्सिमम नंबर ऑफ एक्टिविटीज लिख के बता देनी है किये फोर है और कौन सी एक्टिविटीज कितने टाइम पे कहां कौन से स्लॉट में हो रही है। बस वो शेड्यूल आपको बता देना है। है ना बहुत ज्यादा सिंपल?एक्टिविटी सिलेक्शन एकदम सिंपल है। जो पहले फिनिश हो रहा है बस उसको मतलब ऐसे ऑर्डर में अरेंज करो एंड बस बीच में कोई नहीं आना चाहिए। दैट्स इट। ये तो बच्चों वाला काम है। हम तो कब से मतलबये ऐसे क्वेश्चंस आ जाए तो सब पास हो जाए। है ना?ये क्वेश्चंस आते हैं। तो प्लीज इस ड को बिल्कुल भी मतलब ज्यादा टफ मत समझो। बहुत ज्यादा इजी क्वेश्चन आते हैं एंड बहुत ज्यादा इजी है अगर आप समझ लो तो। ठीक है नाउ दिस वाज़ ऑल अबाउट योर
12. Dynamic Programming Introduction and Optimality Principle
Introduces dynamic programming, overlapping subproblems, optimal substructure, top-down and bottom-up approaches, and explains the principle of optimality with PYQs.
ग्रीडी स्ट्रेटजी। सो चलो गाइस लेट्स स्टार्ट डायनेमिक प्रोग्रामिंग। ये योर डीपी। सो ग्रीडी में हम हर स्टेप पर बेस्ट लुकिंग चॉइस सेलेक्ट करते हैं। ठीक है?लेकिन डायनामिक प्रोग्रामिंग का अप्रोच थोड़ा डिफरेंट है। सपोज तुम्हें एक बड़ा प्रॉब्लम सॉल्व करना है। उसको डायरेक्टली सॉल्व करने के बजाय हम उसे छोटे-छोटे प्रॉब्लम्स में डिवाइड कर देंगे। फिर हर स्मॉल प्रॉब्लम का आंसर कैलकुलेट करेंगे। उससे एकटेबल में स्टोर करेंगे और जब सेम प्रॉब्लम दोबारा आएगा तो उसको रिपीट सॉल्व नहीं करेंगे। डायरेक्ट टेबल से जो है ना हम आंसर उठा लेंगे। बस यही है डायनेमिक प्रोग्रामिंग। एक सिंपल लाइन याद रखो। ब्रेक इंटू स्मॉलर प्रॉब्लम्सप्लस स्टोर आंसर्स प्लस रयूज आंसर्स। दिस इज़ नथिंग बट इक्विवेलेंट टू डायनेमिक प्रोग्रामिंग। ओके?अब मैं सिंपल एग्जांपल से मैं आपको एक्सप्लेन करती हूं। सपोज़ तुम्हें कैलकुलेट करना है 1 + 1 + 1 + 1 + 1 आंसर क्या होगा?फाइव। अब अगर एक और वन ऐड कर दिया तो दोबारा सब कुछ कैलकुलेट करने की जरूरत है क्या?
नहीं। प्रीवियस आंसर फाइव था उसमें वन ऐड कर दो। आपको आंसर क्या मिल जाएगा?सिक्स। सिमिलरली डीपी प्रीवियस कैलकुलेशंस को याद रखता है। ठीक है?आई होप यू अंडरस्टुड दिस थिंग। नाउ देयर आर टू इंपॉर्टेंट प्रॉपर्टीज। ओके?व्हिच अ प्रॉब्लम नीड्स फॉर डीपी। क्लियर?सो सबसे पहले डायनेमिक प्रोग्रामिंग यूज़ करने के लिए हमें इन दोनों को अच्छे से समझना पड़ेगा। फर्स्ट ओवरलैपिंग सब प्रॉब्लम्स मतलब सेम स्मॉल प्रॉब्लम बार-बार रिपीट होती है। फॉर एग्जांपल किसी रिकर्सिव कैलकुलेशन में जैसे इस पर्टिकुलर डायग्राम मेंआप देखो तो C ऑफ़ 2 1 का आंसर मल्टीपल टाइम्स कैलकुलेट हो रहा है। तो डीपी उसका आंसर एक बार ही कैलकुलेट कर लेगा और स्टोर कर लेगा। बस दूसरी बार वो वापस कैलकुलेट नहीं करेगा। वो पुराने आंसरको ही रीयूज करेगा। दिस इज योर ओवरलैपिंग सब प्रॉब्लम्स। ठीक है?सेकंड आपके पास है ऑप्टिमल सबस्ट्रक्चर। मतलब बड़े प्रॉब्लम का ऑप्टिमल आंसर। उसके स्मॉलर सब प्रॉब्लम्स के ऑप्टिमल आंसर्स को कंबाइन करके बनाया जा सकता है। सिंपल वर्ड्स मैं एक्सप्लेन करूं तो अगर स्मॉल प्रॉब्लम्स के बेस्ट आंसर्स को कंबाइन
करके बिग प्रॉब्लम का बेस्ट आंसर मिल सकता है तो ऑप्टिमल सबस्ट्रक्चर प्रेजेंट है। ठीक है?आई होप दिस थिंग इज़ वेरी क्लियर। नाउ देयर आर टू वेज़ टू इंप्लीमेंट डीपी। डायनेमिक प्रोग्रामिंग यूज़ करने के लिए दो बहुत ज्यादा इंपॉर्टेंट प्रॉपर्टीज हैं जो आपको याद रखनी है। क्या जो भी अभी मैंने आपको बताया सिंपलयाद रखो दो वेज़ हैं। क्या वेज़ हैं आपके पास?टॉप डाउन और बॉटम अप। टॉप डाउन को टॉप डाउन को मेमोराइजेशन भी बोला जाता है और बॉटम अप को टैबुलेशन भी बोला जाता है। अब मैं टॉप डाउन की बात करूं तो यहां पर नॉर्मल रिकर्शन ही आपको लिखनाहोता है। लेकिन हर कैलकुलेटेड आंसर को स्टोर करना पड़ेगा। अगर सेम प्रॉब्लम दोबारा आए तो स्टर्ड आंसर ही आप यूज़ करोगे। ठीक है?अब बॉटम अप यानी टैबुलेशन की बात करें तो स्मालेस्ट प्रॉब्लम से स्टार्ट करो। टेबल फिल करते जाओ और ग्रेजुअली फाइनल आंसर तक पहुंच जाओ। ठीक है?
तो एग्जाम न्यूमेरिकल्स में जनरली हम टेबल बनाकर सॉल्व करते हैं। यानी बॉटम अप्रोच का यूज करते हैं। क्लियर?अब सिंपल वर्ड्स में मैं आपको याद करवाऊं तो टॉप डाउन को आप ऐसे याद रखो कि आपके पास है रिकर्शन प्लस मेमोरी। ठीक है?और बॉटम आपके पास है आपके टेबल प्लस लूप्स। ठीक है?तो ये दो वेज़ हैं आपके जिससे आप डीपी इंप्लीमेंट कर सकते हो। क्लियर है?आई होप दिस थिंग इज वेरी वेरी क्लियर। अब मई जून 2025 में आया हुआ क्वेश्चन देखो। विद रिस्पेक्ट टू डायनेमिक प्रोग्रामिंग व्हाट इज द प्रिंसिपल ऑफ ऑप्टिमैलिटी?गिव अ मैथमेटिकल रिप्रेजेंटेशन फॉर द सेम। ठीक है?तो अब आता है एक इंपॉर्टेंट थ्योरी क्वेश्चन दैट इज योर प्रिंसिपल ऑफ़ ऑप्टिमैलिटी। इस प्रिंसिपल को रिचर्ड बेलमैन ने दिया था और इसका सिंपल मीनिंग ये है कि एन ऑप्टिमल सॉल्यूशन कंटेन ऑप्टिमल सॉलशंस टू इट्स सब प्रॉब्लम्स। ठीकहै?एकदम सिंपल एग्जांपल से इसको समझते हैं। सपोज़ हमें A से C तक शॉर्टेस्ट पाथ फाइंड करना है। और शॉर्टेस्ट पाथ आपका है A टू B टू C.
अगर ये ओवरऑल शॉर्टेस्ट पाथ है तो B से C तक का पाथ भी शॉर्टेस्ट होना चाहिए। करेक्ट?यस। अगर B से C तक कोई और शॉर्टेस्ट पाथ अवेलेबल होता तो हम उसको यूज़ करके A से C का पाथ और छोटा बना सकते थे। राइट?यस। इसीलिए ऑप्टिमल सॉल्यूशन का जो यहां पर मतलब है वो ये है कि आप सब प्रॉब्लम्स का ऑप्टिमल सॉल्यूशन भी फाइंड आउट कर रहे हो। क्लियर?तो ऑप्टिमल सॉल्यूशन के सब प्रॉब्लम्स भी ऑप्टिमल होने चाहिए। आई होप दिस थिंग इज़ वेरी वेरी क्लियर। आप एक बार प्रिंसिपल ऑफ़ ऑप्टिमैलिटी को अच्छे से पढ़ लो। एन ऑप्टिमल सीक्वेंस ऑफ डिसीजंस हैस द प्रॉपर्टी दैट व्हाटएवर दइनिशियल स्टेट एंड फर्स्ट डिसीजन आर द रिमेनिंग डिसीजंस मस्ट फॉर्म एन ऑप्टिमल सीक्वेंस विथ रिस्पेक्ट टू द स्टेट रिजल्टिंग फ्रॉम द फर्स्ट डिसीजन। सिंपल वर्ड्स में आप इस एग्जांपल के थ्रू एक्सप्लेन कर सकते हो। क्लियर?
अब इसका मैथमेटिकल रिप्रेजेंटेशन समझते हैं। देखो थोड़ा सा आपको स्टार्टिंग में लगेगा लेकिन इट इज़ वेरी सिंपल। क्लियर?यहां पर ये जो फार्मूला है यहां पर अगर आप इस फार्मूले में देखो आपके पास दिख रहा है आपको s ठीक है s क्या है आपका करंट स्टेट क्लियर और डी ऑफ़ एस क्या है अवेलेबल डिसीजन ओके स्मॉलडी की बात करें तो इट इज़ सिलेक्टेड डिसीजन ओके देन सी ऑफ़ एस कॉमा डी की अगर मैं बात करूं तो ये है करंट डिसीजन की कॉस्ट क्लियर देन टी ऑफ़ एस कॉमा डी की बात करूं तो येहै डिसीजन लेने के बाद का न्यू स्टेट ठीक है देन देन f ऑफ t ऑफ़ s d की बात करूं तो ये है रिमेनिंग प्रॉब्लम का ऑप्टिमल आंसर क्लियर देन ऑपरेटर यहां पर मिनिमम या मैक्सिमम हम यूज़ करसकते हैं एज पर क्वेश्चन क्लियर अब फार्मूला याद रखने की ट्रिक क्या है करंट कॉस्ट प्लस रिमेनिंग ऑप्टिमल कॉस्ट मतलब मिनिमम चाहिए तो मिनिमम चूज़ करो मैक्सिमम चाहिए तो मैक्सिमम चूज़ करो देखो एग्जांपल मैं बताऊं अगर आपको इस
प्रिंसिपल का तो इस प्रिंसिपल का यूज़ मल्टीपल डीपी प्रॉब्लम्स में होता है। तो सपोज अगर मैं आपको बताऊं अ यहां पर तो ठीक है आप इसको ये एग्जांपल के फॉर्म में समझ सकते हो। सबसे पहला है आपके पासशॉर्टेस्ट पाथ यानी कि मिनिमम डिस्टेंस अगर आपको फाइंड करना है तो आप शॉर्टेस्ट पाथ के अंदर इसका यूज़ करते हो। 0 वन नैप्सक के अंदर अगर आपको मैक्सिमम प्रॉफिट फाइंड करना है तो वहां पे आप इस चीज कायूज़ करते हो। मैट्रिक्स चेन मल्टीप्लिकेशन की अगर मैं बात करूं तो यहां पर मिनिमम मल्टीप्लिकेशन कॉस्ट के लिए यह यूज़ होता है। देन ऑप्टिमल बाइनरी सर्च ट्री के अंदर भी मिनिमम सर्च कॉस्ट के लिए ये यूज़ हो रहाहोता है। ठीक है?सो आई होप यू अंडरस्टुड इन सभी प्रॉब्लम्स में स्मॉलर प्रॉब्लम्स के ऑप्टिमल आंसर्स कंबाइन करके फाइनल आंसर कैलकुलेट करते हैं। ठीक है?आई होप दिस थिंग इज़ क्लियर एंड अब आप थ्योरी अच्छे से लिख पाओगे। ओके?
नाउ लेट अस टॉक अबाउट दिस नवंबर दिसंबर 2024 क्वेश्चन। क्वेश्चन इज़ दैट विद रिस्पेक्ट टू डायनेमिक प्रोग्रामिंग व्हाट डू यू अंडरस्टैंड बाय ऑप्टिमल सबस्ट्रक्चर?ठीक है?इसका एकदम सिंपल आंसर अब आप लिख सकते हो कि जो एक प्रॉब्लम है देखो सॉल्यूशन में लिखा हुआ है अ प्रॉब्लम हैज़ ऑप्टिमल सबस्ट्रक्चर इफ इट्स ऑप्टिमल सॉल्यूशन कैन बी बिल्ट फ्रॉम द ऑप्टिमल सॉल्यूशन ऑफ इट्स सब प्रॉब्लम्स।जैसे अभी मैंने आपको ए टू B टू C वाला एग्जांपल दिया है ना?अगर शॉर्टेस्ट पाथ है A टू B टू C सो इफ द कंप्लीट पाथ इज ऑप्टिमल देन द सब पाथ्स मस्ट आल्सो बी ऑप्टिमल। बस यही प्रॉपर्टी आपको एक्सप्लेन करनी है यहां पे। तो आप अच्छे से इसको एक्सप्लेन करसकते हो। यस। सो इसीलिए मैंने जस्ट समरी लिख दी है। ठीक है?नाउ सेकंड यहां पर थर्ड आपका पीवाईक्यू आ गया है मई जून 2024 का। यहां पर क्वेश्चन है कमेंट ऑन द स्टेटमेंट प्रॉब्लम वि डज नॉट सेटिसफाई द प्रिंसिपल ऑफ ऑप्टिमेलिटी कैन नॉट बी सॉल्वड बाय डायनेमिक प्रोग्रामिंग। ओके?
तो यहां पर क्या है?द स्टेटमेंट इज़ ट्रू फर्स्ट ऑफ़ ऑल फॉर द स्टैंडर्ड डायनेमिक प्रोग्रामिंग अप्रोच। अब डायनामिक प्रोग्रामिंग क्या करता है?ये फाइनल आंसर कंस्ट्रक्ट करता है बाय कंबाइनिंग ऑप्टिमल सॉलशंस ऑफ़ स्मॉलर सब प्रॉब्लम्स। ओके?अगर स्मॉलर प्रॉब्लम्स के ऑप्टिमल आंसर्स कंबाइन करने से ओवरऑल ऑप्टिमल आंसर नहीं मिलता तो स्टैंडर्ड डीपी रिकरेंस डायरेक्टली अप्लाई नहीं कर सकते। ठीक है?एग्जांपल की बात करूं मैं तो लॉन्गेस्ट सिंपल पाथ ये इसका एग्जांपल है। सपोज़ आप यहां पर देखो सपोज़ आप A से C तक लॉन्गेस्ट सिंपल पाथ जो है ना देख रहे हो। जैसे है A टू B टू C।ठीक है?लेकिन B से C तक लॉन्गेस्ट सिंपल पाथ निकालते वक्त हो सकता है कि C से B तक किसी रूट से वापस जाना पड़े जिससे वर्टेक्स रिपीट हो सकता है। है ना?तो सिंपल पाथ में वर्टाइससेस रिपीट नहीं कर सकते। इसीलिए ऑप्टिमल सब प्रॉब्लम का आंसर ओवरऑल प्रॉब्लम के कंस्ट्रेंट्स के अंदर डायरेक्टली यूज़ नहीं हो सकता। तो इसका कंक्लूजन आप क्या बता सकते हो कि स्टैंडर्ड डीपी रिक्वायर्स ऑप्टिमल सबस्ट्रक्चर।
अगर प्रॉपर्टी सेटिस्फाई नहीं होती तो रिकरेंस को डायरेक्टली अप्लाई नहीं कर सकते। दैट्स इट। ओके?
13. DP Control Abstraction and Time Analysis
Explains the DP control abstraction template, time complexity formula using distinct subproblems, Fibonacci example, and related previous year questions with answers.
आई होप यू अंडर। नाउ लेट अस अंडरस्टैंड डीपी कंट्रोल एब्स्ट्रैक्शन एंड टाइम एनालिसिस। ठीक है?अब अगेन कंट्रोल एब्स्ट्रैक्शन का मतलब है एल्गोरिदम का जनरल स्ट्रक्चर या फिर टेंपलेट। ओके?अलग-अलग प्रॉब्लम्स हो सकती हैं लेकिन उन्हें सॉल्व करने का जो बेसिक फ्लो होता है वो सिमिलर होता है। तो डायनामिक प्रोग्रामिंग का फ्लो याद रखो। आप सबसे पहले डिवाइड करते हो फिर चेक करते हो फिर स्टोर करते होदेन रीयूज करते हो एंड देन कंबाइन करते हो। एकदम शॉर्ट में मैं ये आपको जो एल्गोरिदम है इसको स्टेप वाइज एक्सप्लेन कर देती हूं। स्टेप वन आप चेक करते हो कि जो प्रॉब्लम है वो स्मॉल इनफ है यानहीं। अगर है तो डायरेक्टली आंसर आप रिटर्न कर देते हो। ठीक है?स्टेप टू, प्रॉब्लम को स्मॉलर सब प्रॉब्लम्स में डिवाइड करते हो। ओके?स्टेप थ्री, आप चेक करोगे कि सब प्रॉब्लम का आंसर टेबल में ऑलरेडी स्टर्ड है या नहीं। स्टेप फोर अगर स्टर्ड है तो रयूज करो। अदरवाइज सॉल्व करके टेबल में स्टोर कर दो। स्टेप फाइव, सब प्रॉब्लम्स के आंसर्स कंबाइन
करके फाइनल आंसर रिटर्न कर दो। ओके?आई होप दिस थिंग इज़ वेरी क्लियर। अब बॉटम अप्रोच की बात करें तो न्यूमेरिकल्स में हम बॉटम अप्रोच ही ज्यादातर यूज करेंगे। ठीक है?तो इसमें पहले स्मालेस्ट सब प्रॉब्लम्स के आंसर्स आप टेबल में फिल करते हैं। फिर उन आंसर्स का यूज़ करके बिगर सब प्रॉब्लम सॉल्व करते हो। ठीक है?फाइनली टेबल से रिक्वायर्ड आंसर आपको मिल जाता है। ओके?आई होप दिस थिंग इज़ वेरी क्लियर। नाउ टाइम कॉम्प्लेक्सिटी की बात करें अगर हम डायनामिक प्रोग्रामिंग से रिलेटेड तो देखो बहुत ज्यादा सिंपल है। अगर आप देख पा रहे हो तो फार्मूला आपके स्क्रीन के ऊपर है। एकदम सिंपलसा फार्मूला है। दैट इज़ t ऑफ़ n = नंबर ऑफ़ डिस्टिंक्ट सब प्रॉब्लम्स इंटू टाइम टू सॉल्व वन सब प्रॉब्लम यूजिंग द टेबल। देखो मतलब दो चीजें आपको कैलकुलेट करनी है। सबसे पहले टोटल कितने डिफरेंट सब प्रॉब्लम सॉल्व
हो रहे हैं। सेकंडली हर सब प्रॉब्लम को सॉल्व करने में कितना टाइम लग रहा है। ठीक है?दोनों को मल्टीप्लाई कर दो। आपको आंसर मिल जाएगा। है ना?बहुत ज्यादा सिंपल। तो बस इसको आपको ऐसे ही समझना है। एंड एक सिंपल एग्जांपल मैं आपको बताती हूं फिबोनसी सीरीज का। ठीक है?सपोज फिबोनकी सीरीज जो है वो आप कैलकुलेट करने जा रहे हो। ओके?अब नॉर्मल रिकर्शन से मैं बात करूं तो सेम वैल्यूस आप बार-बार कैलकुलेट करोगे। इसलिए उसकी जो टाइम कॉम्प्लेक्सिटी है वो एप्रोक्समेटली बिग ऑफ़ 2 n हो सकती है। ओके?लेकिन डायनामिक प्रोग्रामिंग में हम हर फिबोरा की वैल्यू एक बार कैलकुलेट करके स्टोर करते हैं। टोटल n वैल्यूस कैलकुलेट होंगी और हर वैल्यू कैलकुलेट करने में कॉन्स्टेंट टाइम यानी बिगो ऑफ़ वन टाइम लगेगा। ठीक है?इसीलिए आप इसको ऐसे याद रख सकते हो कि उसके बाद जो आपकी एक्सप्पोनेंशियल टाइम कॉम्प्लेक्सिटी होती है ना वो आपकी लीनियर टाइम में चेंज हो जाती है। क्लियर?
सो आई होप दिस थिंग इज वेरी वेरीरी क्लियर। देन आप अगर ये याद रखो ये जो टेबल है है ना?यहां पर आपको एग्जाम में ये चार प्रॉब्लम्स की टाइम कॉम्प्लेक्सिटीज़ आप अच्छे से याद रख सकते हो। आपके पास बायनॉमियल कोफिशिएंट है जिसकी टाइम कॉम्प्लेक्सिटी बिगो ऑफ़ n के है। स्पेस कॉम्प्लेक्सिटी भी बिगो ऑफ़ n के है। वैसेही 0 वन नैपसेट की टाइम कॉम्प्लेक्सिटी बिगो ऑफ़ n है। एंड स्पेस कॉम्प्लेक्सिटी भी सेम है। मैट्रिक्स चेन मल्टीप्लिकेशन की टाइम कॉम्प्लेक्सिटी बिगो ऑफ़ n 3 यानी n है और स्पेस कॉम्प्लेक्सिटी बिगो ऑफ़ n² है। क्लियर?ओबीएसटी ऑप्टिमल बाइनरी सर्चरी की बात करें तो टाइम कॉम्प्लेक्सिटी बिगो ऑफ़ n है और स्पेस कॉम्प्लेक्सिटी बिगो ऑफ़ n² है। अब ये एग्जाम तक ही नहीं अगर आप प्रैक्टिकल्स की बात करो तो वाइवा में भी आपको ये क्वेश्चनबहुत इंपॉर्टेंट है टाइम कॉम्प्लेक्सिटी का। तो प्लीज इस चीज को अच्छे से याद रख लो। और यहां n जनरली टाइम आइटम्स है। ठीक है?
मैट्रसेस या कीस के नंबर को जो है ना ये एन रिप्रेजेंट करता है। नैप्सक में डब्लू जो है वो बैग की कैपेसिटी को को रिप्रेजेंट करता है। और एक इंपॉर्टेंट बात बिगो ऑफ़ एन डब्लू जो है वो सडोपॉलीनोमीयल टाइम है। क्योंकि कॉम्प्लेक्सिटी कैपेसिटी जो है वो डब्लू पर डिपेंड करती है जो इनपुट में रिप्रेजेंट होने के लिए डब्लू के एल्गोरिदम जितने बिट्स भी ले सकती है। ओके?आई होप दिस थिंग इज क्लियर। नाउ लेट अस सी द क्वेश्चन सी नवंबर दिसंबर 2025 में आपको क्वेश्चन आया हुआ है कि राइट अ कंट्रोल एब्स्ट्रैक्शन फॉर द डायनामिक प्रोग्रामिंग स्ट्रेटजी कमेंट ऑन द टाइम कॉम्प्लेक्सिटी ऑफ़ द सब्सट्रैक्शन।तो अभी जो पांच मिनट में हमने जो सारी चीजें पढ़ी है बस उन्हीं को आपको लिखना है। तो बस मैंने इसका सशन नहीं लिखा है क्योंकि वही सारी चीजें आपको रिपीट करनी है। ठीक है?नवंबर दिसंबर 2023 के अंदर जो क्वेश्चन आया है वो देखो। एक्सप्लेन डायनेमिक प्रोग्रामिंग, प्रिंसिपल, कंट्रोल एब्स्ट्रैक्शन, टाइम एनालिसिस ऑफ कंट्रोल एब्स्ट्रैक्शन विद सूटेबल एग्जांपल। तो देखो यही सारी चीज है। एकदम एट मार्क्स का क्वेश्चन आपको ये आया हुआ
है। तो इसके अंदर क्वेश्चन में डायनेमिक प्रोग्रामिंग का आपको प्रिंसिपल लिखना है, कंट्रोल एब्स्ट्रैक्शन लिखना है और टाइम एनालिसिस लिखना है विद द सूटेबल एग्जांपल। बहुत ज्यादा सिंपल है। चलो मैंने समरी लिख दी है। तो मैं एक बारआपको रिवाइज भी करा देती हूं। प्रिंसिपल है सबसे पहले। तो डायनेमिक प्रोग्रामिंग क्या करता है?प्रॉब्लम सॉल्व करता है बाय डिवाइडिंग इट इनू ओवरलैपिंग सब प्रॉब्लम्स। ठीक है?तो उसके अंदर आप क्या करते हो?हर एक सब प्रॉब्लम को एक बार सॉल्व करते हो और उसका आंसर स्टोर कर देते हो एंड बाद में रीयूज करते हो। क्लियर?सो इट रिक्वायर्स ओवरलैपिंग सब प्रॉब्लम्स एंड ऑप्टिमल सबस्ट्रक्चर। तो ये दो प्रॉपर्टीज तो बहुत इंपॉर्टेंट है। हमने पहले भी पढ़ ली है। ओके?पार्ट टू आपको यहां पे पूछा है क्वेश्चन में कंट्रोल एब्स्ट्रैक्शन। तो आपको जनरल डीपी एल्गोरिदम यहां पर लिखनी है। आप सिंपल पांच स्टेप्स लिख सकते हो। देखो फर्स्ट स्टेप आप लिखोगे सॉल्व द बेस केस डायरेक्टली। ठीक है?
सेकंड आप लिखोगे डिवाइड द प्रॉब्लम इंटू स्मॉलर सब प्रॉब्लम्स। थर्ड आप लिखोगे चेक वेदर ईच आंसर इज ऑलरेडी स्टर्ड। क्लियर?फिफ्थ आप लिखोगे इफ स्टर्ड। तो उसको रीयूज कर लो। अदरवाइज कैलकुलेट करके स्टोर कर दो। ठीक है?एंड लास्ट कंबाइन करो आंसर्स को टू कम ऑब्टेन द फाइनल रिजल्ट। ओके। और फाइनल जो आपको क्वेश्चन है जैसे कि टाइम एनालिसिस का पूछा गया है तो जो मैंने आपको अभी फार्मूला बताया भाई वही आपको लिख देना है।t ऑफ़ n इक्वल टू नंबर ऑफ़ डिस्टिंक्ट। सब प्रॉब्लम्स इन टाइम पर अ सब प्रॉब्लम बहुत ज्यादा सिंपल से। ठीक है?तो ये आपने टाइम कॉम्प्लेक्सिटी के बारे में लिख दिया। और एक पॉइंट आप लिख सकते हो कि यहां पर जो एक्सप्पोनेंशियल टाइम कॉम्प्लेक्सिटी वाली प्रॉब्लम्स हैं वो लीनियर टाइम में आ सकती हैं। ठीक है?डीपी का यूज़ करके। तो ये भी एक लाइन आप ऐड कर दोगे तो बहुत अच्छा होगा। एंड एट लास्ट एग्जांपल पूछा है तो भाई फिबोनाकी का आप एग्जांपल दे सकते हो। तो फिबोनाकी जो नॉर्मल वाली होती है रिकर्शन
में वो बिगो ऑफ़ 2 n जो है वो टाइम ले रही होती है बिकॉज़ इट रिपीट्स द कैलकुलेशन। और वही डीपी जो है वो आंसर स्टोर कर लेता है फिबोना की सब प्रॉब्लम्स का। तो यहां पे हमें nवैल्यूज़ होती है टू कैलकुलेट एंड ईच वैल्यू टेक्स बिगो ऑफ़ वन टाइम कॉम्प्लेक्सिटी। तो यहां पर आप जो है इसको ऐसे बता सकते हो कि एट लास्ट बिगो ऑफ़ एन आपकी टाइम कॉम्प्लेक्सिटी हो जाती है। सो दिस शोज़हाउ डायनेमिक प्रोग्रामिंग इंप्रूव्स द एफिशिएंसी। ठीक है?तो ये वाला आंसर आपको बहुत ज्यादा अच्छे से समझ में आ गया है। नाउ नेक्स्ट पीवाईक्यू देख लो। नवंबर दिसंबर 2024 का ये पीवाईक्यू है जिसमें आपको बोला गया है एनलिस्ट द यूजज़ ऑफ़ राइटिंग कंट्रोल एब्स्ट्रैक्शन फॉर एनी
14. Uses of Control Abstraction and Greedy vs DP
Lists six uses of writing control abstractions, then compares greedy and dynamic programming strategies across idea, decisions, optimality, memory, and time complexity.
एल्गोरिथमिक स्ट्रेटजी। ठीक है?बहुत सिंपल है। इसके अंदर आपको यूजज़ एक्सप्लेन करने हैं। है ना?तो मैंने आपके सामने सिक्स पॉइंट्स रखे हैं। बस आप इन सिक्स पॉइंट्स को याद कर लो। एग्जाम में फोर या फाइव पॉइंट्स भी लिख सकते हो डिपेंडिंग ऑन मार्क्स। ठीक है?सबसे पहला है जनरल टेंपलेट। यहां पर आप दिखाते हो यू शो द कॉमन स्ट्रक्चर ऑफ़ एल्गोरिदम्स। ठीक है?कंट्रोल एब्स्ट्रैक्शन का मतलब ही क्या है?आप टेंप्लेट बता रहे हो या फिर एक स्ट्रक्चर बता रहे हो उस एल्गोरिदम को सॉल्व करने का। तो भाई पहला पॉइंट तो यही बन रहा है कि ये जनरल टेंप्लेट है। सेकंड चीज है सेपरेशन ऑफ कंसर्न्स। मतलब किआप सेपरेट करोगे जनरल फ्लो को फ्रॉम द प्रॉब्लम स्पेसिफिक फंक्शनंस। ठीक है?जैसे हमने सेलेक्ट, फिजिबल, कंबाइन ये पढ़ा था। है ना?तो ये बेसिक फंक्शनंस के रूप में हम क्या कर लेते हैं?अपने प्रॉब्लम को डिवाइड कर देते हैं। एंड दिस मेक्स इट वेरी सिंपल। ओके?
थर्ड चीज़ टाइम एनालिसिस। तो यहां पर आपकी जो कॉम्प्लेक्सिटी एनालिसिस होता है वो बहुत ज्यादा इजी हो जाता है समझना। देखो कितना सिंपल सा हमने क्या कर दिया?फार्मूला बना दिया। t ऑफ़ n = n * t सेलेक्ट + t फिजिबल सिंपल से हमें कॉम्प्लेक्सिटी भी समझ में आ जाएगी इससे है ना देन रयूजेबिलिटी की बात करें तो यहां पर सेम स्ट्रक्चर को आप डिफरेंट प्रॉब्लम्समें रयूज कर सकते हो सो दैट इज़ योर रीयूजेबिलिटी देन आपके पास है हेल्प्स इन प्रूविंग करेक्टनेस एंड इन कंपेयरिंग द स्ट्रेटजीस मतलब करेक्टनेस यहां पर इंपॉर्टेंट कीवर्ड है यहां पर इट मेक्स इट इज़ियर टू एक्सप्लेन एंड प्रूवहाउ एन एल्गोरिदम वर्क्स क्लियर देन एट लास्ट इजी इजी टू अंडरस्टैंड, टीच, डीबग। तो यहां पर आपके जो प्रोग्रामर्स है वो अंडरस्टैंड इजीली कर पाते हैं। टीच और डीबग इजीली कर पाते हैं क्या?हमारी एल्गोरिदम्स। बस हर पॉइंट को एक लाइन में आप यहां पर समझ सकते हो एंड अपने हिसाब से क्वेश्चन जो है ना अपना लिख सकते हो। ठीक है?
बहुत ज्यादा इजीली मैंने आपको ये चीजें जो है वो समझा दी है। ठीक है?नाउ लेट अस मूव ऑन टू नेक्स्ट। यहां पर आता है आपका ग्रीडी वर्सेस डायनेमिक प्रोग्रामिंग। तो अब तक हमने ग्रीडी एल्गोरिदम पढ़ा। जहां हम हर स्टेप पर लोकली बेस्ट चॉइस करते थे। ठीक है?लेकिन एक इंपॉर्टेंट क्वेश्चन है क्या हर बार लोकली बेस्ट चॉइस लेने से हमें ग्लोबली बेस्ट आंसर मिलता है?तो सोचो जरा और इसका आंसर आपके पास साफ है नहीं। व्हाई यहां पर देखो और मतलब इसी प्रॉब्लम को समझने के लिए जो है हम ये बेसिक जो ग्रीडी और डायनामिक प्रोग्रामिंग का बीच का डिफरेंस है ये समझनेवाले हैं। ठीक है?तो सबसे पहले जो ग्रीडी है उसको समझ लो। ग्रीडी एल्गोरिदम में हम क्या करते हैं?हर स्टेप पर जो चॉइस उस मोमेंट पर सबसे बेस्ट लगती है वो सेलेक्ट करते हैं। है ना?एक बार चॉइस सेलेक्ट कर ली तो जनरली हम उस डिसीजन को रिकंसीडर नहीं करते। फॉर एग्जांपल अगर आपको फ्रैक्शनल नैप्सक सॉल्व करना है तो हम मैक्सिमम प्रॉफिट पर यूनिट वेट वाला जो ऑब्जेक्ट है वो पहले चूज़ करेंगे। लेकिन
डायनेमिक प्रोग्रामिंग में अप्रोच थोड़ी डिफरेंट है। सी डीपी में हम प्रॉब्लम के डिफरेंट सब प्रॉब्लम सॉल्व करते हैं। उनके आंसर्स सॉल्व करते हैं और फिर उन आंसर्स को कंबाइन करके फाइनल स्यूशन निकालते हैं। ठीक है?मतलब ग्रीडी एक प्रॉमिसिंग पाथ फॉलो करता है। जबकि डीपी मल्टीपल सब प्रॉब्लम्स के आंसर्स को कंसीडर करता है। ठीक है?चलिए अब एग्जाम के लिए इन दोनों का डिफरेंस देखते हैं। बहुत ज्यादा सिंपल है। एंड ये क्वेश्चन नवंबर दिसंबर 2025 में आया हुआ है। कंपेयर ग्रेडी एल्गोरिथमिक स्ट्रेटजी एंड डायनेमिक प्रोग्रामिंग स्ट्रेटजी। तो बहुत ज्यादा इजीली इस चीज कोसमझो। देखो फर्स्ट डिफरेंस है आइडिया है ना?तो ग्रेडी हर स्टेप पर लोकली बेस्ट चॉइस लेता है। ठीक है?जबकि जो डीपी सब प्रॉब्लम सॉल्व करके मतलब हम क्या करते हैं?उनके ऑप्टिमल आंसर्स कंबाइन कर रहे होते हैं। क्लियर?सेकंड है आपके पास डिसीजंस। फाइन। तो ग्रीडी में एक डिसीजन लेने के बाद जनरली हम पीछे नहीं जाते। डीपी में हम रिकरेंस रिलेशन के थ्रू डिफरेंट पॉसिबल चॉइससेस कंसीडर कर सकते हैं। ओके?
थर्ड है आपके पास ऑप्टिमैलिटी। तो यहां पर ग्रीडी हमेशा ऑप्टिमल स्यूशन नहीं देता। वो तब ऑप्टिमल होता है जब मतलब प्रॉब्लम ग्रीडी चॉइस प्रॉपर्टी सेटिस्फाई करती है। फाइन। डीपी सूटेबल रिकरेंस और रिक्वायर्ड प्रॉपर्टीज होने पर ऑप्टिमल सॉल्यूशन निकालसकता है। फाइन। देन फोर्थ डिफरेंस है आपके पास मेमोरी। ग्रीडी में जनरली टेबल मेंटेन करने की जरूरत नहीं होती। डीपी में सब प्रॉब्लम के आंसर स्टोर करने के लिए टेबल या मेमोराइजेशन यूज़ होता है। फाइन। फिफ्थ है आपकेपास टाइम कॉम्प्लेक्सिटी। अगर मैं आपको एकदम सिंपल लैंग्वेज में समझाऊं तो टाइम कॉम्प्लेक्सिटी। अब ग्रीडी एल्गोरिदम अक्सर सॉर्टिंग की वजह से बिगो ऑफ़ n लॉग n टाइम लेती है। डीपी में कॉम्प्लेक्सिटी प्रॉब्लम के अकॉर्डिंग बिगो ऑफ़ n² बिगोऑफ़ n या बिगो ऑफ़ n डब्लू हो सकती है। ठीक है?एग्जांपल्स में याद रखो ग्रीडी के एल्गोरिदम मतलब जो है उसमें आप फ्रैक्शनल नैप्सक जॉब सीक्वेंसिंग एक्टिविटी सेलेक्शन प्रीम्स एल्गोरिदम और क्रिसल्स एल्गोरिदम का यूज़ करते हो। डीपी के एग्जांपल्स में आप यहां पर जीरो वन नैप्सक मैट्रिक्स चेन मल्टीप्लिकेशन
ऑप्टिमल बाइनरी सर्चरी और बाइनरी बाइनॉमियल कोफिशिएंट्स लिख के बता सकते हो। ठीक है?आई होप दिस थिंग इज क्लियर एंड ये क्वेश्चन आपको छह मार्क्स के लिए आया हुआ था। तो इतने सारे पॉइंट्स तो फेयर इनफ है। ठीक है?
15. Greedy Limitations and Binomial Coefficients
Proves with 0/1 knapsack and coin change examples that greedy is not always optimal, then explains binomial coefficients using Pascal's triangle with the 2025 PYQ.
तो आई होप दिस थिंग इज आल्सो वेरी वेरी क्लियर टू यू। नाउ लेट अस मूव ऑन टू द नेक्स्ट पीवाईक्यू क्वेश्चन जो कि अगेन नवंबर दिसंबर 2025 का है। इसमें आपको कमेंट करना है ऑन द स्टेटमेंट ग्रीडी मेथडऑलवेज प्रोवाइड्स द ऑप्टिमल सॉल्यूशन। अब एक बहुत इंपॉर्टेंट थ्योरी क्वेश्चन है। ग्रीडी मेथड ऑलवेज प्रोवाइड्स द ऑप्टिमल सॉल्यूशन। क्या ये स्टेटमेंट ट्रू है या फॉल्स है?तो देखो यहां पर आपको सिर्फ कमेंट करने बोला है। तो बहुत ज्यादा जो मतलब अमाउंट ऑफ स्टूडेंट्स हैं वो क्या करेंगे?इस इस पर्टिकुलर स्टेटमेंट को कंसीडर करके जो है कमेंट करेंगे। मतलब उसी को ट्रू बता के और पूरा पेज भर देंगे। लेकिन अगर आप ये वीडियो देख के जाओगे तो सबसे पहले आप लिखोगे कि भाई ये जो स्टेटमेंटहै ये फॉल्स है। क्योंकि ग्रेडी हर प्रॉब्लम में ऑप्टिमल आंसर नहीं देता। क्योंकि कभी-कभी लोकली बेस्ट चॉइस लेने से फाइनल आंसर सब ऑप्टिमल हो सकता है। इसको एक एग्जांपल से समझते हैं। सपोज हमारे पास जीरो वन नैप्सक प्रॉब्लम
है। नैप्सक की कैपेसिटी है 15। ओके?और ऑब्जेक्ट दिए गए हैं। फर्स्ट ऑब्जेक्ट है जिसका वेट है एट, प्रॉफिट है 10। ठीक है?सेकंड ऑब्जेक्ट है जिसका वेट है सिक्स, प्रॉफिट है एट। थर्ड ऑब्जेक्ट है जिसका वेट है फोर, प्रॉफिट है थ्री। फोर्थ ऑब्जेक्ट है जिसका वेट है टू और प्रॉफिट है फोर। ग्रीडी अप्रोच में हम प्रॉफिट पर यूनिट वेट कैलकुलेटकरते हैं। तो फर्स्ट ऑब्जेक्ट का रेश्यो क्या हो जाएगा?10 / 8 यानी 1.25। सेकंड ऑब्जेक्ट का रेश्यो आपके पास आएगा 8 / 6 यानी अप्रोक्सिममेटली 1.33। थर्ड ऑब्जेक्ट का रेश्यो है 3 / 4 यानी 0.75। फोर्थ ऑब्जेक्ट का रेश्यो है 4 / 2 यानी कि टू। इसीलिएग्रीडी ऑर्डर आपका होगा फोर्थ ऑब्जेक्ट। देन सेकंड ऑब्जेक्ट देन फर्स्ट ऑब्जेक्ट एंड देन थर्ड ऑब्जेक्ट कैपेसिटी आपके पास 15 है तो फोर्थ ऑब्जेक्ट का वेट टू और सेकंड ऑब्जेक्ट का वेट सिक्स लेने के बाद रिमेनिंग कैपेसिटी सेवन होगी।
फर्स्ट ऑब्जेक्ट का वेट एट है। इसीलिए वो फिट नहीं होगा। फाइन। थर्ड ऑब्जेक्ट का वेट फोर है और ग्रीडी एल्गोरिदम यूज़ मतलब ये जो पर्टिकुलर ऑब्जेक्ट है इसको चूज़ नहीं करेगा। तो टोटल प्रॉफिट आपके पास हो जाएगा 4+ 8 + 3 है ना?वो थर्ड ऑब्जेक्ट को भी चूज़ कर लेगा। बिकॉज़ उसका वेट क्या है?फोर है। तो आपके पास टोटल प्रॉफिट हो जाएगा 4 + 8 + 3 व्हिच इज़ 15। लेकिन अगर हम फर्स्ट और सेकंड ऑब्जेक्ट चूज़ करें तो टोटल वेट आपके पास होगा 8 + 6 यानी कि 14 और प्रॉफिटहो जाएगा 10 + 8 यानी 18। देखा ग्रीडी ने प्रॉफिट 15 दिया। लेकिन ऑप्टिमल सॉल्यूशन का जो प्रॉफिट है वो 18 आया। इसीलिए 001 नैप्सक में प्रॉफिट टू वेट रेशो बेस्ड ग्रीडी अप्रोच हमेशा ऑप्टिमल स्यूशन नहीं देती। एकऔर फेमस एग्जांपल है कॉइन चेंज प्रॉब्लम का। ठीक है?अगर कॉइंस हैं वन, थ्री और फोर और हमें अमाउंट सिक्स बनाना है तो ग्रेडी पहले फोर लेगा, फिर वन लेगा, फिर वन लेगा। तो टोटल कॉइंस आपके पास क्या आ गए?
थ्री आ गए। लेकिन ऑप्टिमल सॉल्यूशन है 3 + 3 यानी सिर्फ दो कॉइंस। इसीलिए एग्जाम में कंक्लूजन आपको लिखना पड़ेगा इस क्वेश्चन के लिए कि ग्रीडी इज़ ऑप्टिमल ओनली व्हेन द प्रॉब्लम सेटिस्फाई द ग्रीडी चॉइस प्रॉपर्टी एंड दरिक्वायर्ड ऑप्टिमैलिटी कंडीशंस। आई होप नाउ दिस थिंग इज़ वेरी वेरी क्लियर टू यू। ओके?नाउ लेट्स कम ऑन टू द नेक्स्ट टॉपिक दैट इज़ बायनॉमियल कोफिशिएंट्स यूजिंग डीपी। ठीक है?अब ये जो है डायनामिक प्रोग्रामिंग का एक इंपॉर्टेंट न्यूमेरिकल टॉपिक जो है बायनॉमियल कोफिशिएंट। इसको अच्छे से समझो। इस टॉपिक से डायरेक्ट न्यूमेरिकल क्वेश्चन पूछे जा सकते हैं। इसलिए फार्मूला और टेबल दोनों समझना इंपॉर्टेंट है। ठीक है?सबसे पहले बायनॉमियल कोफिशिएंट को c ऑफ़ n k से रिप्रेजेंट करते हैं। ठीक है?इसका मीनिंग है n ऑब्जेक्ट्स में से k ऑब्जेक्ट्स को कितने डिफरेंट वेज़ में सेलेक्ट कर सकते हैं?आई रिपीट मायसेल्फ। C ऑफ़ N K का मतलब है N ऑब्जेक्ट्स में से K ऑब्जेक्ट्स को कितने डिफरेंट वेज़ में सेलेक्ट कर सकते हैं। फॉर एग्जांपल अगर आपके पास फाइव स्टूडेंट्स हैं और आपको उनमें से टू स्टूडेंट सेलेक्ट
करने हैं तो नंबर ऑफ़ वेज़ होंगे जैसे C ऑफ़ 5 2 ये आपको देगा 10। ठीक है?इसको फैक्टोरियल फॉर्मूले से भी कैलकुलेट कर सकते हैं। तो आपके पास फैक्टोरियल फार्मूला क्या होता है इसका?c ऑफ़ n k = nोरियल / kोरियल * n - kोरियल ठीक है लेकिन फैक्टोरियल मेथड में लार्ज वैल्यूस के लिए कैलकुलेशंस एक्सपेंसिव हो सकती हैं। डायनेमिक प्रोग्रामिंग में हम पास्कल्स ट्रायंगल का यूज़ करके आंसर्स एफिशिएंटली कैलकुलेट करतेहैं। ठीक है?अब इंपॉर्टेंट रिकरेंस रिलेशन की बात करते हैं। एग्जाम में सबसे इंपॉर्टेंट फार्मूला है बायनॉमियल कोफिशिएंट की रिकरेंस रिलेशन। अगर k = 0 है। देखो आपके सामने नजर आ रहा है k = 0 है या k = n हैतो आंसर वन होगा। मैथमेटिकली c ऑफ़ n0 एंड c ऑफ़ nn = 1 बाकी केसेस में आपका पूरा प्रॉपर फार्मूला लगता है। दैट इज c ऑफ़ n k = c ऑफ़ n - 1 k - 1 + c
ऑफ़ n - 1 k इसका सिंपल मीनिंग है करंट वैल्यू प्रीवियस रो की दो वैल्यूस का सम होती है। ठीक है?अब फॉर एग्जांपल c ऑफ़ 4 2 इसका आंसर क्या आएगा?इसका आंसर आएगा एज़ पर फार्मूला C ऑफ़ 3 1 + C ऑफ़ 3 2 दैट इज = 3 + 3 व्हिच इज़ सिक्स। इसी तरह हम पूरा टेबल फिल कर सकते हैं। आई होप दिस थिंग इज़ वेरी क्लियर।अब देखो ये है आपकी एल्गोरिदम बायनॉमियल की। ठीक है?इस एल्गोरिदम को समझते हैं। सबसे पहले एक टू डायमेंशनल टेबल C क्रिएट करेंगे। ठीक है?आउटर लूप आई है। आई आउटर लूप आई ज़ीरो से N तक चलेगा। ये रोज़ रिप्रेजेंट करेगा। इनर लूप J 0 से मिनिमम ऑफ़ i एंड K तक चलेगा। अगर J = 0 है या J = i है तोC ऑफ़ आई जे को वन असाइन करेंगे। अदरवाइज रिकरेंस रिलेशन अप्लाई करेंगे। कौन सा रिकरेंस रिलेशन?
वही फार्मूला c ऑफ़ ij है व्हिच इज़ = c ऑफ़ i - 1 j - 1 + c ऑफ़ i - 1 * j फाइनली रिटर्न आप कर दोगे c ऑफ़ n * k यानी हर वैल्यू एक हीबार कैलकुलेट होगी और टेबल में स्टोर हो जाएगी। ठीक है?अब टाइम एंड स्पेस कॉम्प्लेक्सिटी की बात करें तो यहां पर अगर आप देखो अगर हम पूरा n / k टेबल फिल करते हैं तो टाइम कॉम्प्लेक्सिटी बिगो ऑफ़ n * k होगी और स्पेस कॉम्प्लेक्सिटी भी बिगो ऑफ़ n* k होगी। अगर हम एक सिंगल रो डीपी अप्रोच यूज़ करें तो स्पेस कॉम्प्लेक्सिटी बिगो ऑफ़ K तक रिड्यूस हो सकती है। ठीक है?एग्जाम में अगर गिवन एल्गोरिदम टू डायमेंशनल टेबल यूज़ कर रहा है तो आंसर लिखो। टाइम कॉम्प्लेक्सिटी इज़ इक्वल टू बिगो ऑफ़ NK एंड स्पेस कॉम्प्लेक्सिटी इज़ अगेन इक्वल टू बिगो ऑफ़ NK। आई होप दिस थिंग इज़ वेरी क्लियर।
नाउ वी हैव अ नवंबर दिसंबर 2025 पीवाईक्यू जिसमें आपको बायनॉमियल कोफिशिएंट फाइंड आउट करना है ऑफ़ x + y n जहां पर आपके n की वैल्यू गिवन है फाइव। ठीक है?बहुत सिंपल है। देखो यहां पर बहुत ज्यादा आपको इसको अच्छे से समझना है। यहां पर हम पास्कल्स ट्रायंगल का टेबल रो बाय रो कंस्ट्रक्ट करेंगे। सबसे पहली रो में सिर्फ वन होगा। ठीक है?मैं यहां पर अगर आपको दिखाऊं सबसे पहली रो में आपके पास सिर्फ वन होगा। ठीक है?देन रो वन के अंदर आपके पास क्या आ जाएगा?1 रो टू के अंदर आपके पास आ जाएगा 1 2 1 रो थ्री के अंदर आपके पास है 1 3 1 रो फोर में आपके पास है 1 4 6 4 1 और रो फाइव में आपके पास है1 5 10 5 1 ये है रिक्वायर्ड बायनॉमियल कोफिशिएंट्स। अब समझते हैं कि ये वैल्यू्यूज आई कहां से है?
है ना?तो आपके पास है C ऑफ़ चलो C ऑफ़ 2 1 अगर हमें कैलकुलेट करना है तो इसके लिए हम प्रीवियस रो की वैल्यूस ऐड करेंगे। यानी कि C ऑफ़ 2 1 अगर मुझे फाइंड आउट करना है तो मेराफार्मूला मुझे बताएगा C ऑफ़ 2 1 = C ऑफ़ 1 0 + C ऑफ़ 1 व्हिच इज़ इक्वल टू 1 + 1 एंड C ऑफ़ 2 1 की वैल्यू आपके पास आ गई टू। क्लियर?अब सिमिलरली C ऑफ़ 3 1 की बात करें तो इसका फार्मूला बनेगा C ऑफ़ 2 0 + C ऑफ़ 2 1 वि इज इक्वल टू 1 + 2 व्हिच इज = 3 है ना?वैसे ही C ऑफ़ 4 2 की बात करूं तो इट इज़ इक्वल टू C ऑफ़ 3 1 + C ऑफ़ 3 2 व्हिच इज़ इक्वल टू 3 + 3 व्हिच इज़ इक्वल टू 6। ठीक है?
देन लास्टली c ऑफ़ 5 2 की बात करूं तो इट इज़ इक्वल टू C ऑफ़ 4 1 + C ऑफ़ 4 2 व्हिच इज इक्वल टू 4 + 6 व्हिच इज इक्वल टू 10। इसी तरह आप पूरा टेबलकंस्ट्रक्ट करते हो। ठीक है?रिमेंबर पास्कल्स ट्रायंगल में हर इंटरनल एलिमेंट अपने ऊपर वाली रो के दो एडजेसेंट एलिमेंट्स का सम होता है। अब बायनॉमियल थ्योरम अप्लाई करते हैं। तो फार्मूला आपके पास क्या है?देखो फार्मूला यहां पर आपके पास क्या है?x + y n = समेशन ऑफ़ c ऑफ़ n k x n - k * y k तो फॉर n = 5 कोफिशिएंट्स आपके होंगे 1 5 10 5 1 देयर फॉर आपके x + y 5 का फार्मूलाबनेगा x 5 + 5x 4y + 10x y² + 10x x²y + 5x y 4 + y 5 ठीक है?तो फाइनल आंसर बायनॉमियल कोफिशिएंट्स का आपके पास बायनॉमियल कोफिशिएंट्स आए 1 5 10 5 1 और अगर क्वेश्चन में n इक्व 4 हो तो कोफिशिएंट्स होंगे 1 4 6 4 1 एग्जाम में रिकरेंस रिलेशन डीपी टेबल सिंपल कैलकुलेशंस
और फाइनल एक्सपेंशंस लिखना मत भूलना। ठीक है?आई होप ये तो अब आपको बहुत ज्यादा क्लियर हो गया है। ठीक है?
16. 0/1 Knapsack Using Dynamic Programming
Explains the 0/1 knapsack recurrence relation, DP table algorithm, and solves the repeated PYQ with capacity 5 including traceback to identify selected items.
सो नाउ लेट्स मूव ऑन टू द नेक्स्ट थिंग। तो यहां पर सी ओके अब हम डायनेमिक प्रोग्रामिंग का एक बहुत इंपॉर्टेंट टॉपिक स्टार्ट कर रहे हैं। व्हिच इज़ जीरो वन नैप्सक प्रॉब्लम। अब इस टॉपिक को ध्यान से समझनाक्योंकि यूनिवर्सिटी एग्जाम्स में इससे एट या 10 मार्क्स का न्यूमेरिकल क्वेश्चन पूछा जाता है। ठीक है?सबसे पहले नैप्सक का मीनिंग बताओ। मैंने स्टार्टिंग में ही आपको बता दिया है। नैप्सक का मीनिंग है बैग। है ना?सपोज आपके पास एक बैग है और उस बैग की मैक्सिमम कैपेसिटी 5 केg है। आपके पास मल्टीपल ऑब्जेक्ट्स हैं और हर ऑब्जेक्ट का एक वेट और एक प्रॉफिट है। आपको ऐसे ऑब्जेक्ट सेलेक्ट करने हैं कि टोटल वेट बैगकी कैपेसिटी से एक्सीड ना करे और टोटल प्रॉफिट मैक्सिमम हो। अब यहां एक इंपॉर्टेंट कंडीशन है जीरो वन नैप्सक में हम किसी ऑब्जेक्ट को डिवाइड नहीं कर सकते एज वी डू इन फ्रैक्शनल नैप्सक। ओके?
या तो ऑब्जेक्ट को कंप्लीटली सेलेक्ट करेंगे या बिल्कुल सेलेक्ट नहीं करेंगे। ठीक है?फॉर एग्जांपल अगर किसी ऑब्जेक्ट का वेट 3 kg है और प्रॉफिट 20 है तो हम उस ऑब्जेक्ट का 1 केg लेकर बाकी 2 केg छोड़ नहीं सकते। इसी वजह से ग्रीडी अप्रोच हर बार ऑप्टिमल सॉल्यूशन नहीं देता। हमेंडायनेमिक प्रोग्रामिंग की हेल्प लेनी पड़ती है। डीपी में हम एक टेबल बनाएंगे जिसमें डिफरेंट आइटम्स और डिफरेंट कैपेसिटीज के लिए मैक्सिमम पॉसिबल प्रॉफिट स्टोर होगा। ठीक है?आई होप कि आपको मैंने टॉपिक अच्छे से समझा दिया है 0 वन नैप्सक का। अब रिकरेंस रिलेशन समझो। बहुत सिंपल है। देखो हम यहां पर V ऑफ़ आई डब्लू से यहां पर इसको रिप्रेजेंट करेंगे कि फर्स्ट आई आइटम्सयूज़ करके कैपेसिटी W के अंदर मैक्सिमम कितना प्रॉफिट अचीव कर सकते हैं। ठीक है?यहां पे अगर आप देखो तो आई इज इक्वल टू नंबर ऑफ़ आइटम्स कंसीडर्ड। W इक्वल टू करंट नैप्सक कैपेसिटी। wi = वेट ऑफ आइटम आई ओके pi = प्रॉफिट ऑफ आइटम आई सबसे पहले बेस केस अगर जीरो आइटम्स
हैं तो प्रॉफिट ज़ीरो होगा क्लियर और अगर कैपेसिटी ज़ीरो है तो भी प्रॉफिट ज़ीरो होगा। ठीक है?मैथमेटिकली देखें तो v ऑफ़ 0W = 0 एंड v ऑफ़ i0 = 0 अब हर आइटम के लिए हम दो पॉसिबिलिटीज कंसीडर करेंगे। केस वन आइटम का वेट कैपेसिटी से ज्यादा है। अगर wi इज ग्रेटर दन w तोआइटम बैग में फिट नहीं होगा। इसीलिए हम उस आइटम को स्किप कर देंगे। ठीक है?तो v ऑफ़ i w = v ऑफ़ i - 1 w केस टू आइटम बैग में फिट हो सकता है। है ना?अगर w ऑफ़ i इज लेस ैन इक्वल टू w तो हम दो चॉइससेस कंपेयर करेंगे। चॉइस वन आइटम को सेलेक्ट मत करो। ठीक है?तो प्रॉफिट होगा आपके पास क्या?V ऑफ़ i - 1 w चॉइस टू आइटम को सेलेक्ट कर लो। आइटम सेलेक्ट करने पर उसका प्रॉफिट pi ऐड होगा और रिमेनिंग कैपेसिटी होगी w - wi इसीलिए प्रॉफिट होगा आपके पास pi + v ऑफ़ i -
1 w - wi अब इन दोनों में से मैक्सिमम चूज़ करेंगे तो v ऑफ़ iw = मैक्स ऑफ़ V ऑफ़ i - 1 W ओके प्लस सॉरी कॉमा PI + V ऑफ़ ऑफ़ i - 1 w - wiठीक है?बस यही 0 वन नैपसेट के मेन रिकरेंस रिलेशन है। ठीक है?आई होप दिस थिंग इज क्लियर एंड मैंने यही चीज यहां पर आपको एक्सप्लेन की है। ठीक है?अब एल्गोरिदम को सिंपल लैंग्वेज में समझते हैं। सबसे पहले टेबल की फर्स्ट रो और फर्स्ट कॉलम को जीरो से इनिशियलाइज करेंगे। उसके बाद आइटम्स के लिए आई आउटर लूप और कैपेसिटी के लिए इनर लूप रन करेंगे। हर सेलपर चेक करेंगे कि करंट आइटम फिट होता है या नहीं। अगर फिट नहीं होता तो प्रीवियस रो की वैल्यू कॉपी कर देंगे। अगर फिट होता है तो आइटम को लेना और यहां पर लेना है या नहीं लेना है
ये प्रॉफिट कंपेयर करने से हम डिसाइड करेंगे और मैक्सिमम वैल्यू को स्टोर कर देंगे। फाइनली टेबल के लास्ट सेल यानी v ऑफ़ एन डब्लू में मैक्सिमम प्रॉफिट मिल जाएगा। टाइम कॉम्प्लेक्सिटी की बात करें तो हम n आइटम्स औरw कैपेसिटी वैल्यूस के लिए टेबल फिल करते हैं। इसीलिए टाइम कॉम्प्लेक्सिटी है आपके पास बिगो ऑफ़ NW और टेबल में बिगो ऑफ़ NW सेल्स ही आप स्टोर करते हो। ठीक है?देन स्पेस कॉम्प्लेक्सिटी की बात करें तो इट इज़ बिगो ऑफ़ NW अगेन। यहां एक इंपॉर्टेंट पॉइंट है बिगो ऑफ़ NW सूडो पॉलीनोमीयल कॉम्प्लेक्सिटी है। मैं रिपीट कर रही हूं अपने आपको। क्योंकि ये कैपेसिटी W की न्यूमेरिकल वैल्यू परडिपेंड करती है। सिर्फ उसके इनपुट साइज पर नहीं। ठीक है?आई होप दिस थिंग इज वेरी क्लियर। नाउ यहां पर ये क्वेश्चन है। देखो आपके पास पीवाईक्यू यहां पर ये नवंबर दिसंबर 2023 और मई जून 2023 में रिपीट हुआ है। तो यू हैव टू फाइंड द ऑप्टिमल सॉल्यूशन फॉर
ज़ीरो वन नैपक इंस्टेंस यूजिंग डायनेमिक प्रोग्रामिंग। और कैपेसिटी यहां पर W = 5 गिवन है। आइटम्स हैं। वेट कॉमा प्रॉफिट के फॉर्मेट में गिवन है। ठीक है?ये सारे 1 2 3 4 आपके पास जो है ना ऑब्जेक्ट्स हैं। क्लियर?तो यहां पर देखो बहुत ज्यादा सिंपल। इसको हम अच्छे से समझते हैं। यहां पर एकदम सिंपल। ये जो है डीपी टेबल आप यहां पर बनाओगे। रोज़ आइटम्स रिप्रेजेंट करेंगी और कॉलम्स जो है वो कैपेसिटी जीरो से फाइव तकरिप्रेजेंट करेंगे। ठीक है?अब रो जीरो की मैं बात करूं। जब कोई आइटम अवेलेबल नहीं है तो हर कैपेसिटी पर मैक्सिमम प्रॉफिट जीरो होगा। क्लियर?जीरो। अब रो वन की मैं बात करूं तो अब आइटम वन कंसीडर करते हैं जिसका वेट टू और प्रॉफिट 12 है एस पर क्वेश्चन। तो कैपेसिटी जीरो और वन पर आइटम फिट नहीं होगा। इसीलिए प्रॉफिट जीरो रहेगा। ठीकहै?क्या बोला मैंने?
कैपेसिटी जीरो और वन पर आइटम फिट नहीं होगा। इसीलिए प्रॉफिट जीरो रहेगा। कैपेसिटी टू से फाइव तक आइटम फिट हो जाएगा। इसीलिए प्रॉफिट 12 होगा। क्लियर?अब रो टू की अगर मैं बात करूं तो अब आइटम टू ऐड करते हैं। कैपेसिटी वन पर आइटम टू फिट होता है तो प्रॉफिट 10 मिलेगा। कैपेसिटी टू पर हम कंपेयर करेंगे तो सिर्फ आइटम वन प्रॉफिट 12 देरहा है और सिर्फ आइटम टू प्रॉफिट 10 दे रहा है। तो मैक्सिमम 12 है। तो कैपेसिटी थ्री पर दोनों आइटम सेलेक्ट कर सकते हैं और टोटल वेट आपके पास होगा 2 + 1 वि इज इक्वल टू 3 औरप्रॉफिट 12 + 10 व्हिच इज इक्वल टू 22। इसीलिए कैपेसिटी थ्री पर आंसर 22 होगा। इसी तरह टेबल की बाकी रोज़ आप फिल करेंगे। वैसे ही रो थ्री की मैं बात करूं तो आइटम थ्री का वेट थ्री औरप्रॉफिट 20 है। कैपेसिटी थ्री पर आइटम थ्री लेने से प्रॉफिट 20 मिलता है। लेकिन प्रीवियस आइटम से 22 मिल रहा था। इसीलिए मैक्सिमम 22 रहेगा। कैपेसिटी फोर पर आइटम थ्री को आइटम टू के साथ सेलेक्ट कर सकते हैं।
टोटल वेट 3 + 1 व्हिच इज इक्वल टू 4 है। टोटल प्रॉफिट 20 + 10 व्हिच इज इक्वल टू 30 होगा। इसीलिए V ऑफ़ 3 4 विल बी इक्वल टू 30 क्लियर है?अब कैपेसिटी फाइव पर आइटम थ्री के साथ आइटम टू और आइटम फाइव में से बात जो बेस्ट कंपैटिबल कॉम्बिनेशन है वो कंसीडर हम करेंगे। मैक्सिमम प्रॉफिट 32 आता है। अब रो फोर की मैं बात करूं एट लास्ट तोयहां पर आइटम फोर का वेट टू और प्रॉफिट 15 है। कैपेसिटी थ्री पर लाइक बेस्ट प्रॉफिट 25 है। और कैपेसिटी फोर पर जो बेस्ट प्रॉफिट है वो 30 है। और कैपेसिटी फाइव पर आइटम फोर का जो को मतलबआइटम थ्री और आइटम टू के साथ हमें सेलेक्ट करने से वेट मिल जाएगा 2 + 3 + 1 वि इज़ सिक्स। जो कैपेसिटी से ज्यादा है। इसीलिए ये कॉम्बिनेशन अलाउड नहीं है। लेकिन आइटम फोर और आइटम्स वन और
टू का जो कॉम्बिनेशन है वो हम चेक कर सकते हैं। उसका टोटल वेट 2 + 2 + 1 यानी 5 हो जाएगा और प्रॉफिट 15 + 12 + 10 37 हो जाएगा। देयर फॉर जो फाइनल मैक्सिमम प्रॉफिट आपकाआएगा वो आएगा 37। आई होप आपको स्टेप वन बहुत इजीली समझ में आ चुका है। क्लियर?यही चीजें मैंने आपको एक्सप्लेन करी है। स्टेप टू की बात करते हैं व्हिच इज़ ट्रेस बैक। यानी अब आपको आइडेंटिफाई करना है सिलेक्टेड आइटम्स को। अब देखो यहां पर सिर्फ मैक्सिमम प्रॉफिट लिखना इनफ नहीं है। हमें ये भीबताना है कि कौन से आइटम सेलेक्ट हुए। है ना?तो ट्रेस बैकक हमेशा लास्ट कॉल से स्टार्ट होता है। हम V ऑफ़ 45 देख रहे हैं। व्हिच इज़ 37 यहां से स्टार्ट करेंगे। ठीक है?कंपेयर करेंगे V ऑफ़ 45 और V ऑफ़ 35 को व्हिच इज़ 37 एंड 32 37 32 के इक्वल है क्या?
नहीं है। इसका मतलब आइटम फोर सिलेलेक्ट हो गया। ठीक है?आइटम फोर का वेट टू है तो रिमेनिंग कैपेसिटी बची 5 - 2 व्हिच इज़ इक्वल टू 3 अब V ऑफ़ 3 देखो व्हिच इज़ इक्वल टू 22 और V ऑफ़ 2 3 देखो व्हिच इज़ इक्वल टू 22 दोनोंइक्वल है तो आइटम थ्री सेलेक्ट नहीं हुआ। ठीक है?अब V ऑफ़ 2 3 देखो व्हिच इज़ इक्वल टू 22 और V ऑफ़ i 3 देखो व्हिच इज इक्वल टू 12 दोनों डिफरेंट है इसीलिए आइटम टू सेलेक्ट हुआ। ठीक है?रिमेनिंग कैपेसिटी बची 3 - 1 व्हिच इज़ इक्वल टू 2। अब V ऑफ़ i 2 देखो व्हिच इज़ 12 और V ऑफ़ 0 2 देखो व्हिच इज़ ज़ीरो। दोनों डिफरेंट है तो आइटम वन भी सिलेक्ट हुआ। फाइनल सिलेक्टेडआइटम्स हैं 1, 2 एंड फोर। टोटल वेट है 2 + 1 + 2 वि इज इक्वल टू 5 और टोटल प्रॉफिट है 12 + 10 + 15 वि इज इक्वल टू 37 देयर फॉर जो मैक्सिमम प्रॉफिट आपका आया
वो आया 37 आई होप नाउ दिस थिंग इज वेरी क्लियर टू यू ऑल गाइस ओके यही चीज मैंने आपको एक्सप्लेन करी अभी क्लियर वेरी वेरी क्लियर अगर नहीं समझ में आया तो एक बार और रिपीट करके जो हैआप इसको देख सकते हो पर अच्छे से समझ लो क्योंकि क्वेश्चन जो है वो आपका इसमें पूछा जा रहा है। ठीक है?
17. Second 0/1 Knapsack PYQ and DP Limitations
Solves another 0/1 knapsack PYQ with capacity 7 showing where greedy fails, then discusses situations where DP struggles such as large capacity and memory requirements.
सिमिलर क्वेश्चन यहां पर आपको पूछा गया है फॉर वेट इक्वल टू से। है ना?वेट इक्वल टू से के लिए ये क्वेश्चन आपको यहां पर पूछा गया है और आपको ऑप्टिमल सॉल्यूशन फाइंड आउट करना है यूजिंग डीp। चलो मैं आपको एक्सप्लेन करती हूं। मेरा काम है सारे न्यूमेरिकल्स आपको इजी लगे तो मैंआपको अच्छे से एक्सप्लेन करती हूं। देखो स्टेप वन है आपका। तो यहां पर आप दूसरा देखो सिंपल चीज़ है। यहां पे कैपेसिटी सेवन है और फोर आइटम्स हैं। दैट इज़ ए, बी, सी और डी। ठीक है?आइटम ए का वेट वन और प्रॉफिट वन है। आइटम बी का वेट थ्री और प्रॉफिट फोर है। क्लियर?वैसे ही आइटम सी का वेट फोर और प्रॉफिट फाइव है। आइटम डी का वेट फाइव और प्रॉफिट सेवन है। हम कैपेसिटी जीरो से सेवन तक डीपी टेबल बनाएंगे। सबसे पहले आइटम ए कंसीडर करेंगे। इसका वेट सिर्फ वन है
और प्रॉफिट वन है। तो कैपेसिटी वन से ऑनवर्ड प्रॉफिट वन रहेगा। अब आइटम बी ऐड करते हैं। कैपेसिटी थ्री पर आइटम बी का प्रॉफिट फोर है। जो आइटम ए के प्रॉफिट वन से ज्यादा है। इसीलिए V ऑफ़ B3 की मैं बात करूं तो ये है फोर। ठीक है?कैपेसिटी फोर पर हम आइटम बी और आइटम ए दोनों सेलेक्ट कर सकते हैं। टोटल वेट आएगा 3 + 1 व्हिच इज़ इक्वल टू 4। टोटल प्रॉफ़िट आएगा 4 + 1 व्हिच इज़ = 5। इसीलिए V ऑफ़ B 4व्हिच इज़ अह की जो वैल्यू है वो आएगी 5। अब आइटम सी कंसीडर करते हैं। कैपेसिटी फोर पर आइटम सी का प्रॉफिट फाइव है। ये प्रीवियस बेस्ट प्रॉफिट के इक्वल है। इसलिए मैक्सिमम फाइव रहेगा। कैपेसिटी फाइव पर आइटमसी और आइटम ए का कॉम्बिनेशन बनेगा। वेट आएगा 4 + 1 = 5 एंड प्रॉफिट आएगा 5 + 1 = 6। ठीक है?
इसीलिए V ऑफ़ C 5 की वैल्यू सिक्स आ गई। कैपेसिटी सेवन पर आइटम सी और आइटम बी को सेलेक्ट कर सकते हैं। वेट 4 + 3 आएगा वि इज इक्वल टू से एंड प्रॉफिट 5 + 4 आएगा व्हिचइज इक्वल टू न। इसीलिए V ऑफ़ C की वैल्यू आ गई नाइन। अब आइटम डी ऐड करते हैं। कैपेसिटी सिक्स पर आइटम बी और आइटम ए का प्रॉफिट एट होगा। लेकिन कैपेसिटी सेवन पर आइटम डी को आइटम बीके साथ सेलेक्ट करने के लिए टोटल वेट 5 + 3 यानी एट चाहिए जो अलाउड नहीं है। इसीलिए आइटम डी ऐड करने के बाद भी कैपेसिटी से पर मैक्सिमम प्रॉफिट नाइन ही रहेगा। सो आई होप कि ये चीजआपको बहुत अच्छे से समझ में आ गई है। सेकंड स्टेप स्टेप है आपका ट्रेस बैकक। ठीक है?तो अब ट्रेस बैक करते हैं। लास्ट सेल है आपकी V ऑफ़ D 7 व्हिच इज़ नाइन। ठीक है?
कंपेयर करेंगे V ऑफ़ D 7 व्हिच इज़ और V ऑफ़ C, 7 को। तो दोनों इक्वल है यानी नाइन और नाइन। इसीलिए आइटम D सेलेक्ट नहीं हुआ। ठीक है?अब V ऑफ़ C 7 वि इज न और V ऑफ़ B 7 वि इज फाइव। दोनों डिफरेंट है इसलिए आइटम C सिलेलेक्ट होगा। क्लियर?रिमेनिंग कैपेसिटी की बात कर रहे हैं तो हमारे पास 7 - 4 3 बची। अब V ऑफ़ B, 3 जो है फोर और V ऑफ़ A, 3 है वन। दोनों डिफरेंट है इसलिए आइटम B ही सेलेक्ट होगा। ठीकहै?रिमेनिंग कैपेसिटी 3 - 3 0 हो गई। अब बैग की कैपेसिटी कंप्लीटली यूज हो चुकी है। सिलेक्टेड आइटम्स हैं बी और सी। क्लियर?टोटल वेट आया 3 + 4 7 और टोटल प्रॉफिट आया 4 + 5 9 देयर फॉर मैक्सिमम प्रॉफिट आपका क्या बना?नाइन बना। अब व्हाई डस ग्रीडी फेल हियर?
एक छोटा सा ऑब्जरवेशन है। अगर हम प्रॉफिट टू वेट रेशियो यूज़ करते हैं तो आइटम डी का रेशियो 7/5 व्हिच इज 1.4 है जो सबसे हाई है। ग्रीडी पहले डी सेलेक्ट करेगा उसके बाद रिमेनिंग कैपेसिटी टू होगी। आइटमए सेलेक्ट करने पर टोटल प्रॉफिट एट होगा। लेकिन डीपी ने आइटम्स बी और सी सेलेक्ट करके प्रॉफिट नाइन दिया। इसीलिए इस एग्जांपल में ग्रीडी फेल करता है। जबकि डीपी जो है वो ऑप्टिमल आंसर देता है। ठीक है?आई होप नाउ दिस थिंग इज़ वेरी वेरी क्लियर टू ऑल ऑफ़ यू। फाइन। ओके। नाउ यही मैंने यहां पर लिखा हुआ है। ग्रीडी वुड फेल ओवर हियर। ओके?देन यहां पर ये नवंबर दिसंबर 2024 का क्वेश्चन है। अंडर व्हाट सिचुएशन डू यू थिंक द डायनेमिक प्रोग्रामिंग अप्रोच फॉर अ सॉल्विंग अ नैपसेट प्रोग्राम और प्रॉब्लम माइट स्ट्रगल टू फाइंड द ऑप्टिमल स्यूशन। तो ये देखो ये पांचपॉइंट्स हैं। वेरी लार्ज कैपेसिटी डब्लू यूज मेमोरी रियल वेट्स फ्रैक्शनल आइटम्स अलाउड एंड मल्टीपल कंस्ट्रेंट्स। इन चीजों को अगर हम देखें तो ये लिमिटेशन है आपके डायनेमिक प्रोग्रामिंग की। ठीक है?
तो सिंपल इनको आप एक्सप्लेन कर सकते हो। आई थिंक कि एकदम सिंपल लैंग्वेज में अंडर लाइक व्हाट सिचुएशनंस माइट डायनेमिक प्रोग्रामिंग स्ट्रगल टू फाइंड द ऑप्टिमल स्यूशन। तो एकदम सिंपल लैंग्वेज में अगर ऐसा क्वेश्चन आए या फिर लिमिटेशंसऑफ़ डीपी आए तो ये चार पांच पॉइंट्स आप याद रखो। चलो मैं आपको एकदम सिंपल लैंग्वेज में समझा देती हूं। आपको याद रहेगा। जैसे मैंने फर्स्ट बोला वेरी लार्ज कैपेसिटी w है ना?तो 0 वन नैप्सक की टाइम कॉम्प्लेक्सिटी है बिग ऑफ़ एन डब्लू। राइट?अगर कैपेसिटी W बहुत लार्ज हो तो टेबल फिल करना कंप्यूटेशनली एक्सपेंसिव हो सकता है। फॉर एग्जांपल अगर W1 बिलियन हो तो टेबल प्रैक्टिकली बहुत लार्ज हो जाएगा। राइट?या तो दैट इज द फर्स्ट थिंग। सेकंड है ह्यूज मेमोरी रिक्वायरमेंट। तो स्टैंडर्ड डीपी टेबल में अप्रोक्सिममेटली n * W सेल्स जो है वो स्टोर होते हैं। है ना?इसीलिए लार्ज N और W के केस में मेमोरी रिक्वायरमेंट बहुत ज्यादा हो सकती है। है ना?
थर्डली रियल डेसिमल वेट्स। तो स्टैंडर्ड डीपी टेबल डिस्क्रीट इंटीजर कैपेसिटीज यूज करता है। अगर वेट्स 2.37 या 4.65 जैसे डेसिमल नंबर्स में हो तो डायरेक्टली इंटीजर इंडेक्स टेबल यूज़ नहीं कर सकते। राइट?स्केलिंग या अल्टरनेटिव एल्गोरिदम की जरूरत पड़ सकती है। फाइन। फोर्थ अगर हम देखें तो इट इज़ फ्रैक्शनल आइटम्स। है ना?तो ज़ीरो वन नैप्सक में आइटम्स को ब्रेक नहीं कर सकते। अगर फ्रैक्शनल क्वांटिटीज अलाउड है तो स्टैंडर्ड जीरो वन डीपी फॉर्मुलेशन एप्लीकेबल नहीं है। फ्रैक्शनल नैप्सक के लिए ग्रेडी अप्रोच यूज कर सकते हैं। ठीक है?एंड एट लास्ट मल्टीपल कंस्ट्रेंट्स। तो अगर वेट के साथ वॉल्यूम, कॉस्ट या दूसरी कंस्ट्रेंट्स भी हो तो डीपी टेबल मल्टीडमेंशनल हो सकता है। इससे टाइम और स्पेस दोनों रिक्वायरमेंट्स रैपिडली इनक्रीस हो सकती हैं। कंक्लूजन में लिखो कि डीपीऑप्टिमल स्यूशन दे सकता है। लेकिन लार्ज कैपेसिटी, मेमोरी रिक्वायरमेंट्स और एडिशनल कंस्ट्रेंट्स के वजह से इसका प्रैक्टिकल एग्जीक्यूशन जो है वो डिफिकल्ट हो सकता है। ठीक है?
आई होप आई होप दिस थिंग इज नाउ वेरी वेरी क्लियर। एंड नाउ जो मेन चीजें हैं वो आपकी बहुत क्लियर हो चुकी हैं। एंड मोस्ट ऑफ न्यूमेरिकल्स हमने कवर कर लिए हैं। ठीक है?
18. Matrix Chain Multiplication Concept and PYQ
Explains why multiplication order matters in matrix chains, the recurrence relation, algorithm, and solves the May-June 2024 PYQ finding optimal parenthesization with cost 94.
अब हम आ जाते हैं एकदम सिंपल। क्या कौन सा पार्ट है?बहुत इंपॉर्टेंट टॉपिक है ये आपका एमसीएम दैट इज़ मैट्रिक्स चेन मल्टीप्लिकेशन। तो इस टॉपिक का जो नाम है ये थोड़ा कॉम्प्लिकेटेड लग सकता है। बट कांसेप्ट एक्चुअली काफी सिंपल है। सपोज़ हमारे पास मल्टीपल मैट्रसेस हैं। A1, A2, A3एंड सो ऑन। हमें इन मैट्रसेस को मल्टीप्लाई करना है। अब क्वेश्चन ये है कि हम मैट्रसेस को किस ऑर्डर में मल्टीप्लाई करें ताकि जो मिनिमम नंबर ऑफ स्केलर अब मल्टीप्लिकेशंस हैं वो हम परफॉर्म करें। ओके?एकदम कम परफॉर्म करें। अब यहां एक इंपॉर्टेंट बात समझना। हम मैट्रसेस का ऑर्डर चेंज नहीं कर सकते। हम सिर्फ उनके ब्रैकेट्स चेंज कर सकते हैं। ठीक है?फॉर एग्जांपल अगर हमें a1 a2 a3 मल्टीप्लाई करने हैं तो हम दो वेज़ में कर सकते हैं। कैसे?फर्स्ट a1 * a2 ब्रैकेट के अंदर। ठीक है?इंटू A3 ब्रैकेट के बाहर। सेकंडली a1 ब्रैकेट के बाहर। ओके?
इंटू ब्रैकेट के अंदर a2 * a3 है ना?मैथमेटिकली दोनों का फाइनल आंसर सेम होगा। लेकिन इन दोनों को कैलकुलेट करने का जो कॉस्ट है वो डिफरेंट हो सकता है। और एमसीएम का मेन ऑब्जेक्टिव है इसी कॉस्ट को मिनिमाइज करना। रिमेंबर एमसीएम में मैट्रसेस का मल्टीप्लिकेशन नहींबल्कि मल्टीप्लिकेशन का ऑप्टिमल ऑर्डर फाइंड करना होता है। ठीक है?आई होप नाउ दिस थिंग इज वेरी क्लियर। चलो एक एग्जांपल से समझते हैं कि ऑर्डर मैटर क्यों करता है। ओके?सपोज हमारे पास थ्री मैट्रसेस हैं। A1 है 10 * 100, A2 है 100 * 5 एंड A3 है 5 * 50। क्लियर?मैट्रिक्स मैट्रिक्स मल्टीप्लिकेशन का जो बेसिक फार्मूला है वो याद रखो। अगर हम P * Q मैट्रिक्स को Q * R मैट्रिक्स से मल्टीप्लाई करते हैं तो स्केलर मल्टीप्लिकेशंस की जो टोटल कॉस्ट होती है वो होती है P *Q * R। अब फर्स्ट ऑर्डर कंसीडर करो। A1 * A2 ब्रैकेट के बाहर A3। पहले A1 और A2 मल्टीप्लाई होंगे। कॉस्ट होगा 10 * 100 * 5 वि इज 5000। रिजल्टिंग मैट्रिक्स का साइज होगा 10 * 5। अब
इस रिजल्ट को A3 यानी 5 * 50 मैट्रिक्स से मल्टीप्लाई करेंगे तो कॉस्ट आएगा 10 * 5 * 50 व्हिच इज़ 2500। टोटल कॉस्ट आएगा 5000 + 2500 व्हिच इज़ इक्वल टू 7500 मल्टीप्लिकेशंस। अब सेकंड ऑर्डर कंसीडर करो।A1 * ब्रैकेट के अंदर A2 * A3 पहले A2 और A3 मल्टीप्लाई होंगे। कॉस्ट होगा 100 * 5 * 50 वि इज इक्वल टू 25000 रिजल्टिंग मैट्रिक्स का साइज होगा 100 * 50 अब A1 को इस रिजल्ट सेमल्टीप्लाई करेंगे तो कॉस्ट आएगा 10 * 100 * 50 व्हिच इज 50000 अब टोटल कॉस्ट अगर आप देखो तो आएगा 25000 + 50000 व्हिच इज इक्वल टू 75000 मल्टीप्लिकेशंस अब नोटिस करो फर्स्ट ऑर्डर में सिर्फ 7500 ऑपरेशंस लगेजबकि जबकि सेकंड ऑर्डर में 75,000 मतलब सेम मैट्रसेस सेम फाइनल रिजल्ट बट कैलकुलेशन कॉस्ट 10 टाइम्स डिफरेंट। इसी प्रॉब्लम को सॉल्व करने के लिए हम मैट्रिक्स चेन मल्टीप्लिकेशन एल्गोरिदम यूज़ करते हैं। ठीक है?
अब ये नजर आ रहा होगा आपको रिकरेंस रिलेशन। ठीक है?तो इसका सबसे इंपॉर्टेंट पार्ट है रिकरेंस रिलेशन। सब एकदम इजी लैंग्वेज में इसको समझो। लेट m ऑफ़ i j रिप्रेजेंट द मिनिमम नंबर ऑफ स्केलर मल्टीप्लिकेशंस रिक्वायर्ड टू मल्टीप्लाई मैट्रसेस a i से a j तक ठीक है सबसेपहले बेस केस देखो अगर i = j मतलब हमारे पास सिर्फ एक मैट्रिक्स है एक सिंगल मैट्रिक्स को मल्टीप्लाई करने की जरूरत नहीं होती देयर फॉर m ऑफ i i क्या हो गया ज़ीरो हो गया अब अगर मल्टीप्लाईमतलब हम मल्टीपल मैट्रसेस हैं उनको देखें तो हम उन्हें किसी एक पोजीशन के पर स्प्लिट कर सकते हैं। फॉर एग्जांपल A1, A2, A3, A4 की चेन को हम A1 तक और A2 से A4 तक स्प्लिट कर सकते हैं।या A1 से A2 तक और A3 से A4 तक। हर पॉसिबल स्प्लिट के लिए तीन कॉस्ट कैलकुलेट करनी होती है। लेफ्ट फर्स्ट आपका आएगा लेफ्ट पार्ट को मल्टीप्लाई करने की मिनिमम कॉस्ट। सेकंड राइट पार्ट को मल्टीप्लाई करने की
मिनिमम कॉस्ट। और थर्ड दोनों रिजल्टिंग मैट्रसेस को आपस में मल्टीप्लाई करने की कॉस्ट। ठीक है?तो अगर मैट्रिक्स डायमेंशंस P ऑफ़ i - 1 * p ऑफ़ i है तो फाइनल मल्टीप्लिकेशन की कॉस्ट क्या होगी?p ऑफ़ i - 1 * p ऑफ़ * p ऑफ़j। इसीलिए रिकरेंस रिलेशन है mij = मिनिमम ऑफ़ mi k + m ऑफ़ k + 1 j + p ऑफ़ i - 1 * p ऑफ़ * p ऑफ़जे वेयर k रेंजेस फ्रॉम i टू j - 1 सिंपल वर्ड्स में हर पॉसिबल ब्रैकेट प्लेसमेंट ट्राई करो और जिसकी टोटल कॉस्ट मिनिमम हो उसको सेलेक्ट कर लो। एक एडिशनल टेबल एस ऑफ आई जे भी मेंटेन करते हैं।इसमें हम वो स्प्लिट पोजीशन के स्टोर करते हैं जहां मिनिमम कॉस्ट मिलती है। ये टेबल बाद में ऑप्टिमल पैरेंथजाइजेशन फाइंड करने में हेल्प करती है। क्लियर?आई होप नाउ दिस थिंग इज वेरी वेरी क्लियर टू यू। ठीक है?
अब एल्गोरिदम को समझते हैं। सबसे पहले सिंगल मैट्रसेस की जो कॉस्ट है वो आप जीरो इनिशियलाइज करेंगे क्योंकि एक एक मैट्रिक्स को मल्टीप्लाई नहीं करना पड़ता। उसके बाद चेन लेंथ l को टू से n तक इनक्रीस करेंगे। ठीकहै?हर चेन लेंथ के लिए हम स्टार्टिंग इंडेक्स i और एंडिंग इंडेक्स j कैलकुलेट करेंगे। फिर i से j - 1 तक हर पॉसिबल स्प्लिट के ट्राई करेंगे। हर स्प्लिट के लिए टोटल कॉस्ट कैलकुलेट करेंगे। लेफ्ट कॉस्ट प्लस राइटकॉस्ट प्लस फाइनल मल्टीप्लिकेशन कॉस्ट। अगर यह कॉस्ट अब तक की मिनिमम कॉस्ट से कम है तो मिनिमम कॉस्ट अपडेट कर देंगे और स्प्लिट पोजीशन k को s ऑफ i j में स्टोर कर लेंगे। ठीक है?फाइनली m ऑफ़ 1 n मिनिमम मल्टीप्लिकेशन कॉस्ट रिटर्न करेगा और एस टेबल से हम ऑप्टिमल ऑर्डर रिकंस्ट्रक्ट कर सकते हैं। अब टाइम कॉम्प्लेक्सिटी की बात बात करते हैं। इस एल्गोरिदम में तीन नेस्टेड लूप्स हैं। इसीलिए टाइम कॉम्प्लेक्सिटी ऑब्वियसली
क्या होगी?बिगो ऑफ़ n और m और s नाम की दो टेबल स्टोर होती हैं जिनका साइज n * n है। देयर फॉर स्पेस कॉम्प्लेक्सिटी आपकी यहां पर होगी बिगो ऑफ़ n² एग्जाम में एल्गोरिदम के साथ टाइम और स्पेस कॉम्प्लेक्सिटीभी मेंशन करना गाइस। ठीक है?आई होप नाउ दिस थिंग इज़ वेरी वेरी क्लियर टू यू। ओके?चलो अब मे जून 2024 का पीवाईक्यू देख लो। यहां पर हमें बोला है कि आपके पास चार मैट्रसेस हैं। A1, A2, A3 और A4। ठीक है?यू हैव टू फाइंड द ऑप्टिमल सीक्वेंस ऑफ़ चेन मैट्रिक्स मल्टीप्लिकेशन यूजिंग द डायनेमिक प्रोग्रामिंग अप्रोच। क्लियरली गिव द फाइनल सीक्वेंस एंड द टोटल नंबर ऑफ़ मल्टीप्लिकेशंस इनवॉल्व। ठीक है?तो यहां पर डायमेंशंस एरे होगा आपका P = 3 5 4 2 4 ठीक है?हमें मिनिमम मल्टीप्लिकेशन कॉस्ट फाइंड करनी है। तो स्टेप वन आप क्या करोगे?चेन लेंथ वन यहां पर देखोगे तो सिंगल मैट्रसेस की कॉस्ट जीरो होती है। इसीलिए m1 1 = m2 2 = m3 3 = m4 व्हिच विल बी ऑल इक्वल टू 0 ठीक है?
तो ये स्टेप वन हो गया। स्टेप टू है आपके पास चेन लेंथ टू। ठीक है?यहां पर सबसे पहले एडजेसेंट जो मैट्रसेस है आप उन्हें मल्टीप्लाई करते हो। क्लियर?फॉर a1 एंड a2 कॉस्ट विल बी इक्वल टू 3 * 5 * 4 व्हिच इज इक्वल टू 60। अब a2 और a3 के लिए देखो तो कॉस्ट विल बी इक्वल टू 5 * 4 * 2 व्हिच इज इक्वलटू 40। अब A3 एंड A4 के लिए देखो कॉस्ट इज इक्वल टू 4 * 2 * 4 वि इज 32 इसीलिए M1 2 = 60 m2 3 = 40 एंड m3 4 = 32 क्लियर अब स्टेप थ्री देखलो चेन लेंथ थ्री जिसके पास है। अब थ्री मैट्रिसेस की चेन्नस कंसीडर करेंगे। फर्स्ट A1 से A3 तक दो पॉसिबल ब्रैकेट्स हैं। ऑप्शन वन A1 * ब्रैकेट के अंदर A2 * A3 इसकी कॉस्ट होगी 40 प्लस ब्रैकेट में
3 * 5 * 2 व्हिच इज इक्वल टू 70 क्लियर?ऑप्शन टू है आपके पास ब्रैकेट में a1 * a2 ब्रैकेट के बाहर * a3 इसकी कॉस्ट होगी 60 + 3 * 4 * 2 व्हिच इज इक्वल टू 84 मिनिमम कॉस्ट आपके पास आ गई यहां पर 70 तोयहां पर m1 3 के लिए क्या कंसीडर करेंगे 70 कंसीडर करेंगे अब वहीं पे m2 4 देखो वही सेम प्रोसीजर है आपके पास ऑप्शन वन a2 * ब्रैकेट में a3 * a4 कॉस्ट आपके पास पास आ जाएगा 32+ 5 * 4 * 4 वि इज इक्वल टू 112 क्लियर ऑप्शन टू है आपके पास ब्रैकेट में a2 * a3 * a4 ठीक है कॉस्ट आ जाएगा 40 प्लस ब्रैकेट में 5 * 2 * 4 वि इज80 अब दोनों में मिनिमम हो जाएगा आपके पास 112 और 80 में से 80 है ना देयर फॉर m2 4 की वैल्यू आ गई आपके पास 80 है ना एंड लास्टली लेंथ आपको चेन लेंथ फोर कंसीडर करनी अब
कंप्लीट चेन A1, A2, A3, A4 की मिनिमम कॉस्ट फाइंड करेंगे। तो तीन पॉसिबल स्प्लिट पॉसिबल है। है ना?पोजीशंस हैं। तो सबसे पहले ऑप्शन वन आपके पास आ सकता है। A1 * ब्रैकेट के अंदर A2, A3, A4 है ना?तो इसका कॉस्ट क्या आएगा?0 + 80 + 3 * 5 * 4 वि इज इक्वल टू 140 ओके। ऑप्शन टू a1 * a2 * सेकंड a3 * a4 तो कॉस्ट आएगी 60 + 32 + 3 * 4 * 4 व्हिच इज 140ऑप्शन थ्री की बात करें तो a1 * a2 * a3 ब्रैकेट के अंदर और ब्रैकेट के बाहर * a4 कॉस्ट आ जाएगा 70 + 0 + ब्रैकेट में 3 * 2 * 4 दैट इज इक्वल टू 94 तोतीनों ऑप्शंस में मिनिमम कॉस्ट 94 है। इसीलिए m1 4 की वैल्यू आ जाएगी 94। क्लियर?आई होप कि ये सारी चीजें आपको अच्छे से समझ में आ गई हैं। ओके?
एट लास्ट आप ऑप्टिमल ऑर्डर यानी ऑप्टिमल पैरेंथसाइजेशन यहां पर करते हो। तो स्प्लिट टेबल से पता चलता है कि फर्स्ट स्प्लिट A3 के बाद होता है। इसीलिए चेन को पहले A1, A2, A3 और A4 में स्प्लिट करेंगे। तोA1 * A2 * A3 ब्रैकेट के अंदर और ब्रैकेट के बाहर A4। अब A1 A2 A3 के लिए ऑप्टिमल स्प्लिट A1 के बाद है। देयर फॉर फाइनल पैरेंथसाइजेशन जो आपका बनेगा वो बनेगा A1 ठीक है?इंटू ब्रैकेट के अंदर A2 * A3 ब्रैकेट के बाहर A4 मिनिमम नंबर ऑफ़ स्केलर मल्टीप्लिकेशंस कितने हैं?40 40 + 30 + 24 दैट इज़ 94.Okay?अब टाइम कॉम्प्लेक्सिटी की बात करें तो इट इज़ बिग O ऑफ़ N ओके?ठीक है?और स्पेस कॉम्प्लेक्सिटी की बात करें तो इट इज़ बिगो ऑफ़ n²। आई होप ये भी चीज आपको बहुत अच्छे से समझ में आ गई होगी। ओके?
19. More MCM Practice and OBST Introduction
Provides additional matrix chain multiplication problems for self-practice, then introduces optimal binary search trees, search frequency concept, and the DP recurrence for OBST.
नाउ लेट्स मूव ऑन टू द नेक्स्ट थिंग। यहां पर आपको गिवन है क्या है?सीक्वेंस गिवन है। अ अगेन 4 10 3 12 27 फॉर फाइव मैट्रसेस ऑफ़ साइज ऑल दिस। यू हैव टू यूज़ डायनेमिक प्रोग्रामिंग टू सॉल्व चेन मैट्रिक्स मल्टीप्लिकेशन। अब जैसे इससे पहले हमने करा है सेम वैसे ही करना है।तो आप जो है ये वाला क्वेश्चन खुद से कंसीडर करके सॉल्व करके देख सकते हो। तो ये वाला क्वेश्चन जो है आप अच्छे से खुद समझ लेना। ठीक है?एक्सैक्ट वैसा ही है जैसा अभी मैंने आपको समझाया है। वैसे ही ये है सिक्स मैट्रसेस वाला है। ठीक है?आप इसको भी बहुत अच्छे से कंसीडर कर सकते हो। बहुत सिंपल से हैं। जस्ट आप अगर इनकी चेन लेंथ वाइज कंसीडर करो ना लेंथ वन, लेंथ टू, लेंथ थ्री, लेंथ फोर, लेंथ फाइव, लेंथ सिक्स। अब आप उसको कितनेटाइम लेके चलोगे?जितने नंबर का मैट्रिक्स है आपका बस उतने टाइम आप कंसीडर करके चलोगे क्योंकि अब मैं यहां पे आपको ये न्यूमेरिकल्स एक-एक समझाते बैठूंगी तो बहुत टाइम हो जाएगा। मैंने आपको एक अच्छे से समझा दिया। बस उसी को आपको
समझ के एंड आगे के सारे खुद से करने हैं। एंड देखो ये बहुत ज्यादा सिंपल है। सबके जो ऑप्टिमल ऑर्डर्स है, मिनिमम मल्टीप्लिकेशंस है ये मैंने प्रॉपर आंसर्स के अंदर जो है वो मेंशन कर दिया है। ठीक है?आई होप कि ये दो जो न्यूमेरिकल्स हैं ये आप खुद से कैलकुलेट करोगे और अच्छे से जो है ना इनको सॉल्व कर लोगे। ठीक है?नाउ लेट अस मूव ऑन टू द लास्ट टॉपिक एंड देखो इस पर्टिकुलर टॉपिक के सिर्फ दो ही पीवाईक्यूस जो है ना वो आए हुए हैं। तो इतना ज्यादा इंपॉर्टेंट भी नहीं है लेकिन हां आपको स्किप नहीं करना चाहिए।तो अगर आपको ये पूरा यूनिट काफी बड़ा लग चुका है तो आप मतलब आई विल सजेस्ट कि थोड़ा ब्रेक लेके देख लो नहीं तो फिर स्किप कर दो। इतना कुछ नहीं है। लेकिन अगर आ गया तो फिर आपकोप्रॉब्लम हो सकती है। तो थोड़ा समझ लो। एंड ओबीएसटी तो ऑलरेडी हमने पहले पढ़ रखा है। तो मैं आपको जो है ना डिस्क्रिप्शन में भी लिंक दे दूंगी। आई बटन में भी लिंक दे दूंगी। ओबीएसटी ऑलरेडी मैंने आपको
डीएसए में पढ़ाया हुआ है। तो अगर आपको यहां नहीं समझा है कांसेप्ट की मैं बात कर रही हूं। यहां नहीं समझे तो कांसेप्ट वहां पर समझ लेना। वहां पर मैंने प्रॉपर बोर्ड पे आपको जो है ना चीजें समझाईहै। ठीक है?एंड अगर याद है तो बहुत ही अच्छी बात है। चलो मैं आपको रिवाइज करवा देती हूं। अब यहां पर डायनेमिक प्रोग्राम का यह काफी इंपॉर्टेंट टॉपिक है क्या?ओबीएसटी यानी ऑप्टिमल बाइनरी सर्च ट्री। देखो नाम देखो इसका ऐसा है। सब हमें सब पता है लेकिन जो कांसेप्ट है वो काफी सिंपल है। सबसे पहले हमें पता है कि बाइनरी सर्च ट्री में अगर हम किसी एलिमेंट कोसर्च करते हैं तो उसे फाइंड करने के लिए कुछ कंपैरिजंस करने पड़ते हैं। है ना?अब इमेजिन करो कि तुम्हारे पास कुछ कीस हैं और हर की को सर्च करने की फ्रीक्वेंसी डिफरेंट है। कुछ कीस को हम बहुत फ्रीक्वेंटली सर्च करते हैं और कुछ कीस को रेयरली सर्च करते हैं। फॉर एग्जांपल मान लो
तुम्हारी वेबसाइट पर तीन पेजेस हैं। होम, कोर्सेज और कांटेक्ट। होम पेज को यूजर सबसे ज्यादा विजिट करते हैं। कोर्सेज को जो है ना उससे कम यूज करते हैं और कांटेक्ट को तो सबसे कम यूज करते हैं। अब अगरहोम पेज को ट्री के बहुत नीचे रख दिया तो उसे सर्च करने में ज्यादा कंपैरिजनंस लगेंगे। बट अगर होम पेज को रूट के पास रखा तो वो बहुत जल्दी मिल जाएगा। तो ओबीएसटी का मेन आईडिया भी यही हैकि जो की ज्यादा फ्रीक्वेंटली सर्च होती है उन्हें जनरली ट्री के ऊपर रखना चाहिए ताकि एक्सपेक्टेड सर्च कॉस्ट मिनिमम हो। ठीक है?लेकिन एक और इंपॉर्टेंट बात हम कीस का ऑर्डर चेंज नहीं कर सकते क्योंकि बीएएस की प्रॉपर्टी मेंटेन करनी होती है। हम सिर्फ डिसाइड करते हैं कि कौन सी की रूट होगी और कौन सी लेफ्ट या राइट सबट्री मेंजाएगी। ठीक है?आई होप नाउ द ओबीएसटी जो कांसेप्ट है इट इज़ वेरी क्लियर। अब कॉस्ट ऑफ बाइनरी सर्च ट्री की मैं बात करूं तो देखो कॉस्ट का फार्मूला है कॉस्ट इज इक्वल टू द सम ऑफ सर्च फ्रीक्वेंसी इन लेवल ऑफ़
दैट की। अब मैथमेटिकली बात करूं तो कॉस्ट आपको स्क्रीन पे दिख रहा है इट इज़ इक्वल टू समेशन ऑफ़ i = 1 से n तक pi * लेवल ऑफ़ ki है ना?यहां पे P आई जो की है इस की जो सर्च प्रोबेबिलिटी या फ्रीक्वेंसी होती है वो है। ठीक है?और लेवल का मतलब है कि की ट्री में किस लेवल पर प्रेजेंट है। इस टॉपिक में रूट का लेवल वन कंसीडर कर रहे हैं। फॉर एग्जांपल अगर किसी की की प्रोबेबिलिटी 0.4 है और वो लेवल टू पर हैतो उसका कंट्रीब्यूशन होगा 0.4 * 2 यानी कि 0.8। इसी तरह हर की का कंट्रीब्यूशन कैलकुलेट करके ऐड कर देंगे। हमें ऐसा बीएसटी बनाना है जिसका टोटल वेटेड सर्च कॉस्ट मिनिमम हो। इसीलिए इसका नाम जो है ना ऑप्टिमलबाइनरी सर्च ट्री है। ठीक है?अब यहां पर देख लो डीपी यानी कि डायनेमिक प्रोग्रामिंग का रिकरेंस गिवन है। तो देखो बहुत सिंपल है कि यहां पर डीपी यूज़ करके ऑब्वियसली जो है वो कैसे सॉल्व करते हैं। सपोज़ हमारे पास सॉर्टेड कीज़ है। K1
इज़ लेस < K2 इज़ लेस दैन K3 लेस देन ऑल टिल KN ओके?हमें जो है यहां पर अब हम सी ऑफ़ आई j को डिफाइन करते हैं एस द मिनिमम कॉस्ट ऑफ एन ऑप्टिमल बीएसटी व्हिच कंटेन के से जे तक कीज़। ओके?अगर इंटरवल में सिर्फ एक की है तो वही की रूट होगी। इसीलिए C ऑफ़ आई आई जो है वो आपका pi बन जाएगा। अब अगर इंटरवल एम्प्टी है तो उसकी कॉस्ट ज़ीरो होगी। अब मान लो हमें कीस आईसे जे तक का ऑप्टिमल बीएएसटी बनाना है। हम हर पॉसिबल की को रूट बनाकर चेक करेंगे। अगर की आर को रूट बनाया तो कीस आई से आर माइनस वन लेफ्ट सबट्री में जाएंगी। है ना?और कीस आर प्लस वन से जे राइट सबट्री में जाएंगी। रूट की कॉस्ट में दोनों सबट्रीज की कॉस्ट ऐड होगी और रूट के नीचे आने की वजह से सबट्री की हर की एक लेवल नीचे चली जाएगी। ठीक है?
इसी वजह से हम टोटल सबट्री वेट भी ऐड करते हैं। तो यहां पर रिकरेंस का जो फार्मूला दिख रहा है वो क्या होगा?इट विल बी c ऑफ़ आईj विल बी इक्वल टू मिनिमम ऑफ़ C ऑफ़ आई r - 1 + C ऑफ़ R + 1 J + W ऑफ़ आईj। यही एग्जैक्ट फार्मूला मैंने आपको जब डीए से पढ़ाया था तोओबीएसटी के अंदर बोर्ड पे लिख के समझाया था। एग्जैक्ट फार्मूला। ठीक है?यहां पे आर आई से जे तक मतलब जो है ना वैरी करेगा और डब्ल्यू आई जे का मतलब है इंटरवल आई से जे तक की सारी फ्रीक्वेंसीज का सम यानी कि इसको हम वेट बोलते थे है ना सिंपलवर्ड्स में हर पॉसिबल रूट ट्राई करो हर रूट की टोटल कॉस्ट कैलकुलेट करो और जो मिनिमम कॉस्ट दे उसे सेलेक्ट कर लो। ठीक है?हम एक रूट टेबल भी मेंटेन करेंगे जिसे r आई j कहते हैं। इस टेबल में स्टोर करेंगे कि इंटरवल आई से जे के लिए कौन सी की ऑप्टिमल रूट है। इसी टेबल की हेल्प से एंड में एक्चुअल ट्री
कंस्ट्रक्ट कर सकते हैं। है ना?ये सब हमने करा हुआ है। जस्ट एक रिवीजन फॉर्म में लेना अगर आपने पहले अच्छे से पढ़ लिया है तो। ठीक है?एंड अगर पहले ही आपने इस टॉपिक को स्किप किया होगा तो देखो भाई फिर से आ गया टॉपिक आपको सताने। चलो अब यहां पर इसके ऊपर जो ये देखो ये एल्गोरिदम एंड ऑल इज नॉट दैटेंट बट आप अच्छे
20. OBST PYQs and Video Conclusion
Solves OBST questions from November-December 2023 and May-June 2023 step by step, verifies the minimum cost of 1.7, and concludes with revision guidance and channel promotion.
से इसको जो है ना कांसेप्ट वाइज समझ सकते हो। अब देखो ये क्वेश्चन कैसे आया था आपको नवंबर दिसंबर 2023 में एक्सप्लेन द डायनेमिक प्रोग्रामिंग अप्रोच फॉर सॉल्विंग प्रॉब्लम्स राइट अ डायनेमिक प्रोग्रामिंग एल्गोरिदम फॉर क्रिएटिंग एन ऑप्टिमल बाइनरीसर्च ट्री फॉर अ सेट ऑफ़ एन कीज़ यूज़ द सेम एल्गोरिदम टू कंस्ट्रक्ट द ओबीएसटी फॉर फोर कीज़ ए बी सी डी विथ प्रोबेबिलिटी 0.1 0.2 0.4 एंड 0.3 ये एग्जैक्ट वही चीज़ है जो हमने डीएसए में करीथी यार एकदम सेम चीज है। चार कीज़ गिवन होती है और चार प्रोबेबिलिटीज गिवन होती है। एंड बस हम अपना फार्मूला लगाते जाते हैं। एंड एट द लास्ट हमें ओबीएसटी मिल जाता है। ठीक है?एक बार मैं आपको अच्छे से एक्सप्लेन कर देती हूं। एंड अगेन मैं रिपीट करूंगी। अगर यहां पे आपको वर्चुअली समझ में नहीं आ रहा है तो आप वो वीडियो एक बार देख लो। आधी देखो। मैं पूरी देखने नहीं
बोल रही हूं। आधी देख लो। आपको कांसेप्ट एकदम क्रिस्टल क्लियर हो जाएंगे। ठीक है?देख लो क्योंकि ये क्वेश्चन 10 मार्क्स के लिए आया हुआ है। तो इसको स्किप करना इज नॉट अ गुड थिंग आई विल सजेस्ट। ओके?चलो आ जाते हैं। अब यहां पर आपको फोर कीज़ है गिवन ए, बी, सी और डी जिनकी सर्च प्रोबेबिलिटीज है 0.1, 0.2, 0.4 एंड 0.3। हमें डायनेमिक प्रोग्रामिंग यूज़ करके ओबीएसटी कंस्ट्रक्ट करना है। तो इसको स्टेप बाय स्टेपसमझो। स्टेप वन हमें सिंगल की इंटरवल्स देखने होंगे। ठीक है?सबसे पहले हर की को इंडिविजुअली हम लोग रूट मान लेंगे। A की कॉस्ट है 0.1, B की कॉस्ट है 0.2, C की कॉस्ट है 0.4, डी की कॉस्ट है 0.3। ये हमारे बेस केसेस हो गए। क्लियर?अब स्टेप टू की बात करें तो हमारे पास टू कीज़ हैं। है ना?यानी कि टू की इंटरवल्स हैं। अब दो-दो कीज़ के इंटरवल सॉल्व करेंगे। पहला इंटरवल है A और B अगर A रूट है तो B लेवल टू पर आएगा। तो कॉस्ट हो जाएगी 0.1 + 2 * 0.2 क्योंकि लेवल
टू पे आ गया बी है ना तो आपके पास टोटल कॉस्ट आ जाएगा 0.5 अगर बी रूट है तो ए लेवल टू पर आएगा और कॉस्ट हो जाएगी 0.2 + 2 * 0.1 विल बी इक्वल टू 0.4 हैना?एकदम सिंपल समझ में आ रहा है। है ना?अब मिनिमम कॉस्ट क्या है दोनों में से?0.5 और 0.4 में से 0.4 तो b रूट बनेगा। अब इंटरवल B और C की बात करें। अगर B रूट है तो कॉस्ट होगी 0.2 + 2 * 0.4 वि इज इक्वल टू 1.0 अगर C रूट है तोकॉस्ट होगी 0.4 + 2 * 0.2 विच इज इक्वल टू 0.8 तो C रूट बनेगा मिनिमम कॉस्ट 0.8 रहेगी। सिमिलरली C और D के इंटरवल में C रूट बनने बनाने पर कॉस्ट वन और D रूट बनाने पर कॉस्ट1.1 आता है। इसीलिए C रूट होगा और मिनिमम कॉस्ट वन होगी। क्लियर?
बहुत सिंपल समझ में आ गया?अब स्टेप थ्री है थ्री की इंटरवल्स को लेके। अब A, B, C के इंटरवल्स को सॉल्व करते हैं। हम A, B और C को वन बाय वन रूट बनाकर चेक करेंगे। मैंने आपको बहुत अच्छे से स्प्लिटिंग मेथड समझायाहुआ है वीडियो में। देखो आई विल सजेस्ट इफ यू वांट टू जस्ट मतलब मेक दिस टॉपिक क्रिस्टल क्लियर तो प्लीज वो वीडियो कंसीडर कर लेना ठीक है या सिंपल से YouTube पर जाकर अगर आप ओबीएसटी बाय एच केऑफिशियल सर्च करोगे तो भी आपको वो वीडियो मिल जाएगी फाइन चलो अब यहां पर अगर मैं थ्री की इंटरवल्स में देखूं तो ए को रूट बनाने पर कॉस्ट 1.4 आ रहा है। B को रूट बनाने पर कॉस्ट 1.1आ रहा है। C को रूट बनाने पर कॉस्ट 1.1 आ रहा है। यहां बी और सी दोनों सेम मिनिमम कॉस्ट दे रहा है। टाई की सिचुएशन में हम किसी भी मिनिमम कॉस्ट रूट को चूज़ कर सकते हैं। इस
सॉल्यूशन में C को रूट चूज़ किया गया है। तो अब B C D के इंटर्व के लिए भी सेम प्रोसेस रिपीट करेंगे। तो मिनिमम कॉस्ट 1.4 आएगा और C रूट बनेगा। ठीक है?अब स्टेप फोर की बात करें तो हमारे पास चारों कीज़ हैं यहां पे। सबसे पहला इंपॉर्टेंट स्टेप यहां पे पूरे इंटरवल A से D तक की कॉस्ट कैलकुलेट करनी है। हम चार पॉसिबिलिटीज चेक करेंगे। A को रूट बनानेपर कॉस्ट 2.4 आ रहा है। D को रूट बनाएंगे तो कॉस्ट 1.9 आ रहा है। C को रूट बना रहे हैं तो कॉस्ट 1.7 आ रहा है। और D को रूट बना रहे हैं तो कॉस्ट टू आ रहाहै। इनमें मिनिमम कॉस्ट है 1.7। तो पूरे के पूरे ट्री का रूट बनेगा C। ठीक है?लेफ्ट सबट्री में A और B आएंगे और राइट सबट्री में D आएगा। ठीक है?तो आप ऐसे करके ऐसे करके यह ओबीएसटी जो है क्रिएट करते हो। ए और बी के इंटरवल के लिए हमने बी को रूट चूज़ किया था। इसलिए बी सी का लेफ्ट चाइल्ड होगा और ए बी का लेफ्ट चाइल्ड
होगा। फाइनल ट्री कुछ ऐसा आपको दिख रहा होगा जिसमें रूट आपके पास सी है। सी का लेफ्ट चाइल्ड बी है। सी का राइट चाइल्ड डी है। और बी का अगर लेफ्ट चाइल्ड देखें तो वो ए है। अब आंसरवेरीफाई करते हैं। देखो सी जो है लेवल वन पर है। बी लेवल टू पर है। डी लेवल टू पर है और ए लेवल थ्री पर है। तो टोटल कॉस्ट अगर हम देखें तो C के लिए आएगी 0.4 *1 दैट इज़ 0.4 B के लिए आएगी 0.2 * 2 दैट इज़ 0.4 D के लिए आएगी 0.3 * 2 व्हिच इज 0.6 A के लिए आएगी 0.1 * 3 व्हिच इज़ 0.3 तो टोटल आएगा 0.4 + 0.4+ 0.6 + 0.3 व्हिच इज़ 1.7। फाइनल आंसर देख लो। तो ओबीएसटी रूट सी है और मिनिमम सर्च कॉस्ट 1.7 है। तो एग्जाम में जो ये फाइनल ओबीएसटी है ये बनाना बहुत जरूरी है और कॉस्ट को वेरीफाई भी
करना जरूरी है। ठीक है?आई होप दिस थिंग इज वेरी क्लियर। एंड एग्जैक्ट सेम सिचुएशन में ये भी क्वेश्चन आया हुआ है जो कि मई जून 2023 में है। इसको मैं इसमें भी आपको कीज़ 10 20 30 40 गिवन है। एंड ये काफीसिंपल है। है ना?क्योंकि इसमें ऐसा डेसिमल में गिवन नहीं है। पहले वाले क्वेश्चन में डेसिमल था। तो अब ये तो और भी सिंपल हो गया और फ्रीक्वेंसी भी प्रॉपर 4 टू 63 गिवन है। तो बस वैसे ही जैसे अभी हमने सॉल्वकिया वैसे ही आपको सॉल्व करना है। एंड इस फॉर्मेट में आपको ओबीएसटी मिल रही होगी। सो आई होप कि आपको ओबीएसटी भी बहुत अच्छे से समझ में आ गई है। एंड वी हैव कवर्ड द एंटायर यूनिट। ठीक है?हमने सारी की सारी चीजें डिटेल में देखी। एंड एक भी क्वेश्चन हमने मिस नहीं किया। सारे के सारे पेपर्स जो अब तक अवेलेबल है डा के वो सारे पेपर्स में से सारे के सारे क्वेश्चन जो है वो हमने
पढ़ लिए हैं। तो आई होप कि अब इस वीडियो के बाद आपके पास सिर्फ काम रहेगा रिवाइज करने का एंड वो रिवीजन आप कैसे करोगे आपको पता है यू विल गो ऑन टू एचपी ऑफिशियल डॉटin वेबसाइट आपको येनोट्स ऑलरेडी अपलोड कर दिए है मैंने जस्ट आपको जाके परचेस करना है एंड अपनी स्टडी स्टार्ट कर देनी है प्लीज डोंट वेट फॉर द लास्ट मोमेंट एंड अगर अभी आप एग्जाम्स के वक्त देख रहे हो तो प्लीज रिवीजनइज वेरीेंट तो प्लीज नोट्स को वेरीफाई करना बिल्कुल मत भूलना एंड रिवाइज कर लेना एग्जाम से पहले ओके चलो दैट दैट्स इट। ये सब आपका रिवीजन शीट है। इसमें मैंने हमने देखो अभी तक कितना सारी चीजें पढ़ ली।हमने फ्रैक्शनल नैप्सक पढ़ा। हमने जॉब सीक्वेंसिंग पढ़ी। मिनिमम पेनल्टी शेड्यूलिंग पढ़ा, एक्टिविटी सिलेक्शन पढ़ा, बायनॉमियल कोफिशिएंट, जीरो वन नैप्सक, मैट्रिक्स चेन, ओबीएसटी एंड ये सारे क्वेश्चंस में आपको न्यूमेरिकल्स पूछे गए हैं। तो गाइस आपको हर एक जो कांसेप्ट
है वो बहुत क्लियर होना चाहिए। तभी आपको न्यूमेरिकल सॉल्व करने में आएगा। एंड देखो मैंने इस शीट में आपको फार्मूलास भी दे दिए हैं और टाइम कॉम्प्लेक्सिटी भी दे दी है। क्योंकि क्वेश्चन में एक सब क्वेश्चन जरूर होताहै कि टाइम कॉम्प्लेक्सिटी लिखो। तो ये आपको अच्छे से पता होना चाहिए। एंड आई होप कि चीजें याद हो गई होंगी। एंड ये सारे के सारे क्वेश्चंस के आंसर्स है। एंड जस्ट यू कैन अंडरस्टैंड बाय सॉल्विंग एवरीथिंग। एंडयस आई होप यू ऑल हैव अंडरस्टुड एवरीथिंग फ्रॉम दिस पर्टिकुलर वीडियो। एंड इस वीडियो में लिटरली बहुत ज्यादा बहुत ज्यादा जो है ना एफर्ट्स लगे हैं। एंड आई वांट ऑल ऑफ यू गाइस टू लाइक दिस पर्टिकुलर वीडियो हाइपदिस वीडियो ताकि ये और भी स्टूडेंट्स तक जल्दी से जल्दी पहुंच जाए। एंड आई वांट ऑल ऑफ यू गाइस कमेंट्स ऑन दिस पर्टिकुलर वीडियो। यह तरीका आपको कैसा लगा एक्सप्लेन करने का?
मैंने काफी चीजें वर्चुअली एक्सप्लेन करने का ट्राई किया है विदाउट यूजिंग माय हैंड रिटन थिंग्स एंड विदाउट यूजिंग मोर एफर्ट्स इन हैंडराइटिंग एंड एवरीथिंग। आई हैव जस्ट मेड थिंग्स वेरी क्लियर विजुअली। आई हैव मेड थिंग्स वेरी इंटरेक्टिव फॉरऑल ऑफ यू गाइस। तो अगर आपको चीजें अच्छे से क्लियर हो गई है तो प्लीज वैसे कमेंट करना एंड आई विल लव टू रिप्लाई ऑल ऑफ यू गाइस। एंड डेफिनेटली अगर आपको वीडियोस हेल्प कर रही है तो बताना।एंड इस वीडियो के बाद आपको कौन से सब्जेक्ट का वीडियो चाहिए यह भी मुझे जरूर बताना। आप जो कमेंट करोगे वही मैं वीडियो लाऊंगी। एंड अगर ऑब्वियस सी बात है अगर आप कमेंट नहीं करोगे तो मैं नेक्स्ट वीडियोलाने से पहले 10 बार सोचूंगी क्योंकि ये वीडियो कोई मुझे पांच दिन लगे हैं। तो जस्ट फॉर यू गाइस टू टेल मी टेल मी कि आपको नेक्स्ट क्या चाहिए?
यही सेम सब्जेक्ट का यूनिट फोर चाहिए या कोई दूसरा सब्जेक्ट चाहिए?प्लीज टेल मी एंड इस वीडियो को लाइक करना बिल्कुल मत भूलना। चैनल पर नए हो तो सब्सक्राइब कर देना। थैंक्स फॉर वाचिंग। बाय।