أولمبياد نسمو المرحلة الثالثة الدرس الثامن Dynamic Programming حل مسألة Vacation

السلام عليكم ورحمه الله وبركاته حياكم الله جميعا من جديد في سلسله الدروس المقدمه من منصه كود في شرح المنهج المتواجد في الامبياات النسمه الدرس السابق قمنا بحل مساله الفراج واحد الان سوف نقوم بحل مساله الفيكيشنز مساله الفيكيشن هي تعتبر سوف نقوم بحلها ايضا على الدايناميك بروجرامين باستخدام الدايناميك بروجرامين لكي نذكر كيفيه منهجيه حل الديانامك بروجرامين دائما قبل كتابه اي كود في البدايه اتذكر لدي عده خطوات لابد معرفه المصفوفات التي سوف اقوم باستخدامها بعد ذلك البيس كيس بعد ذلك سوف يكون لدي البيس كيس بعد ذلك سوف يكون لدي الحاله 90% من مسائل الدايناميك بروجرامين سوف يكون بداخله هذا الشرط اي انه اذا تم حساب الحل من قبل اي انه في كما اتفقنا ان الدي بي نقوم بتخزين الحلول داخلها الحلول التي قمنا بحسابتها مسبقا فاذا كانت لا تساوي الناقص واحد فاي انها محسوبه فالان قم بارجاعها ان لم تكن محسوبه ان لم تكن محسوبه قم بحسابها وطبعا كما تعلمون يعني هذا هو المنهجيه تقريبا 90% من الداينامك مسائل الداينامك بروجرامين يتم حلها بالشكل هذا طيب الان ناتي الى مساله الفيكيشن كما اتفقنا يا جماعه مساله الفيكيشن اي اي قمنا باخذ هذا المنهج وبصياغته بشكل افضل لكي الطالب يصبح لديه القدره على فهم هذه المساله اذا لدينا ثلاث مصفوفات وبي وسي طول كل منها ان فالان ماذا اقوم بتخيل المصفوفات التي اي وبي وس وهذه المصفوفات الثلاثه واحده اثنان ثلاثه من اجل فقط تقريب الصور بعد ذلك اي سوف يكون لدي ايام في كل يوم اي اللي هو من الصفر الى النق واحد نفرض انه ال تساوي ثلاثه تساوي اربعه فسوف يكون لدي صفر 1 ا ثلاثه ايام هذه الايام وهذه النشاطات هذه المصفوفات فسوف تكون ماذا مثلا هذه 10 20 30 اي 10 50 70 مثلا هنا 100 17 20 13 طيب اللي ب الذي سوف يحدث بالشكل التالي ايش يقول لي اي + يجب ان يختلف عن النشاط في اليوم اي يعني ببساطه انه مثلا اذا باليوم الاول ايش بدي اختار النشاط رقم ثلاثه مثلا في اليوم اللي بعده ما يصير ايش مثلا اليوم الثان اليوم الاول اخترت النشاط 20 اليوم اللي بعده ما يحي لا ما يحق لي ارجع اخذ من الاي لا بدي اخذ من البي او السي من نشاطات البي او السي طيب شنو الهدف اوجد اكبر مجموع ممكن للقيم المختاره فاذا اني دائما ابحث عن ايش مثلا هذا اليوم الاول هذا هو اليوم الاول اليوم صفر لدي 10 و60 و100 ما هو اكبر شيء فسوف اقوم باخذ ال 100 الان لو فرضنا ها 170 فرضناها 170 الان لدي اريد ان في اليوم التالي هو اليوم الاول اليوم الثاني الذي اندكسه واحد فماذا لدي 20 و10 و170 طيب الان اكبر شيء انا بدي اكبر شيء هل استطيع انه اخذ 170 لا بد ان اخذ احدى الخيارين ال 20 او العنهجيه حل السؤال يعني هذا هو فكره السؤال بشكل عام انه لدي ايش بدي اوصل اكبر مجموع ممكن للقيم المختاره يعني اخذ اطول زمن يعني تخيلها كنشاط تمام وانت تريد تاخذ اطول نشاط ممكن طيب الان حطيت شيء تقريبي انا قمت مشان ايش من اجل ان يفهم الطالب ما هي كيفيه حل هذه المساله اي من اجل حل هذه المساله تخيلها بالشكل التالي المصفوفات بدل ان تكون بشكل اي سطو قمت وضعها بشكل عام تمام فهذه هي انشطه اليوم الاول هذه هي اوقاتها 10 عفوا الانشطه اي والانشطه والانشطه سي وهذه هي الايام الايام سوف تكون على اليسار اي ففي اليوم مثلا اليوم الاول اللي هو اليوم صفر كما ترون اي استطيع ان انا سوف ابحث عن اكبر شيء اكبر شيء ما هو في هذه الحاله 70 بعد ذلك هل استطيع ان اخذ ال 80 في اليوم التالي لا لابد ان اخذ يا اما 20 او 50 فمثلا سوف اخذ 50 طبعا احنا شنو هو في الدايناميك بروجرامين كما اتفقنا راح نقوم بايش؟ باخذ بدراسه كل الحلول واخذ افضل حلول ممكنه طيب بعد ذلك اخذت ال 50 كما اتفقنا اخذت ال 50 بعد ذلك هل الان ممكن اخذ ايش راح اخذ كوني اخذت من النمط ما يصير ارجع اخذ من البي بدي اخذ يا من الا يا من السي وانا ابحث عن الاكبر فراح اخذ السي وبعد ذلك الان ابحث عن الاكبر لا استطيع الاكبر وين 10 ولا 40 فسوف اخذ ال 40 بعد ذلك اي اكبر ال 50 ولا ال 70 فسوف اقوم باخذ ال 70 وهذا افضل سيناريو وراح يعطيني اكبر قيمه طبعا الدايناميك بروجرامين ما راح تكتفي بهذا الشيء الدايناميك بروجرامين راح تبلش بسيناريو تبدا من العشره وتشوف تبدا من ال 40 وتشوف تبدا من ال 70 وتشوف في كل مره راح يقوم بتخ يقوم بتخزين القيم في كما اتفقنا في الدي بي والقيم هذه سوف نقوم ان ان كانت محسوبه سوف نقوم باخذها بشكل مباشر لم تكن محسوبه سوف نقوم بحسابها طيب كما اتفقنا اي هذا هو منهجيه عملها ان قمنا بتشغيلها مثلا الان تمشي بالشكل هذا 70 نفس ما اتفقنا فيكون الناتج الناتج 320 وهو اكبر شيء ما ما مش الخوارزميه بكافه السيناريات واختارت السيناريو الافضل اللي موجود عننا طيب قد يطرحني سؤال طيب الان ايش بدي اعرف بدي اعرف البيس كيس اللي عندي لابد ان اقوم بمعرفه البيس كيس اللي عندي فالبيس كيس اللي عندي هذه هي في ك ان كانت ايش اليوم الاول لدي يوم واحد ان كان لدي يوم واحد فما اخذ اي نشاط اي يا بي يا سي انا لدي ثلاث حلول صح مثلا لو كان لدي قام المستخدم بادخال يوم واحد اللي هو مثلا ام يوم واحد فسوف يكون ماذا لدي لا بد اختار النشاط اي او النشاط بي او النشاط سي لا يوجد لدي حلول كبيره بس ايش بدي اختار الماكس طيب اي اذا جينا ليه جا على الشروط الاخرى ايش بدنا الشروط الثانيه اللي راح نكتبها راح نكتب ايضا اذا كان النشاط صفر اذا قمنا باختيار النشاط صفر الان سوف لا بد ان نوه على شغله قبل الحل الان لن نرمز للمصفوفات باي وبي وسي بل سوف نرمز لها بصفر وواحد واثنان لماذا؟ لان الرمز لها بهذا الشكل يفصل عليه عندما تكون ارقام افضل فالان مثلا اذا اخذت مثلا كما مشينا قبل قليل اخذت ال 70 ففي المره القادمه ما راح استطيع انه اخذ من التايب اثنين بدي اخذ يا من التايب 50 او من التايب 20 اللي هم يا تايب واحد او تايب صفر فهذا هذول ايش راح اسميهم تايبس هذول راح اسميهم بالكودز التايبس هم صفر وواحد واثنين وهذول الايام طيب فنجي كما اتفقنا ايش المصفوفات اللي عندي مصفوفه دي بي ومصفوفه دي من اجل الايام مصفوفه الدي بي ايش راح اخزن بها راح يكون مصفوفه الدي بي مصفوفه شبيهه لهذه المصفوفه مليئه بالناقص واحدات كما اتفقنا هي سوف تكون مليئه بالناقص واحدات وعندما نقوم بايجاد اي ناتج سوف نقوم مثلا الناتج هنا مثلا كان 300 او مثلا كان ناقص واحد فسوف نقوم بازاله الناقص واحدات ونقوم بالبدء ملء هذه داله الدي بيذا نقوم بملئها بال الامور التي قمنا بحسابها بالنواتج التي قمنا بحسابها طيب كما اتفقنا جد يوجد لدي التايب صفر التايب واحد التايب اثنان فاذا اخذت من التايب صفر انا ايش بدي اخذ مثلا هنا 10 20 30 هذا في اليوم صفر في اليوم واحد 20 40 50 فما الذي سوف يحدث مثلا انا في اليوم الصفر اخذت او مثلا اخذت العشره مثلا نمشي بالسيناريوها تمام اخذت 10 فايش راح يصير عندي اللي عندي خيارين ما اصير ارجع اخذ من التايب صفر بدي اخذ يا من التايب واحد او التايب 2 فالان لدي خيارين صح طيب انا بدي ايش بدي الماكسيموم فرح اخذ الماكس بين التايب واحد والتايب اثنين ايش بدي اخذ من بيناتهم الماكس جميل ولا بد اني ايش ما انسى جمع ايش الاي اوف اي طيب استاذ ايش هي الاي اوف اي الاي اوف اي هي مجموعه القيمه اللي قبل انا كنت واقف ه كم مثلا على العشره فلا بد انه يكون مثلا الناتج هنا يكون 10 زائد ايش الماكس من هذول الماكس من هذول كم؟ 50 ف 50 كم يكون الناتج؟ يكون الناتج 60 ال 60 ها وين راح تتخزن؟ بالدي بي كما اتفقنا هي المصفوفه التي ايش يكون بها مثلا ايضا زائد صفر وواحد واثنين تكون التايب صفر تايب واحد تايب اثنين بها مثلا هنا يومين صفر واحد ايش راح تكون؟ كلها مليئه بالناقص واحدات مليئه بالناقص واحدات عندما اقوم بحساب عندما اقوم بحساب مثلا هنا الدي بي اي صفر الاي صفر التايب صفر الان التايب صفر والاي صفر فاي اي عدد عندي سوف اقوم بمسح هذا العدد ووضع الحاسبه التي قمت بحسابها وهي 60 وهكذا سوف يقوم بملء ازاله الناقص واحدات ويقوم بملئها بالعناصر وبعد ذلك يختار الماكس فيما بينهم لماذا لاننا نبحث عن ماذا اكبر مجموع ممكن اكبر مجموع ممكن لدي طيب الان نذهب الى الكود نذهب الى الكود نعم الان سوف اقوم باخذ هذه الشكل هذا واقوم بوضع الكود هنا نعم لاننا نريد ان نقوم بالتاشير عليها طيب نضع هذه جانبا ونبدا بكتابه الكود اولا ماذا يوجد لدي ماذا يوجد لدي يوجد لدي مصفوفتان مصفوفه الاي كما اتفقنا انه الاي والبي والسي راح يكونون ايش اتفقنا؟ اتفقنا ان نضعهم بتو دايمنشن اراي اللي هي اسمها اي وسوف تحتوي على صفر وواحد واثنان وهو التايب صفر واحد واثان والايام سوف تكون بالشكل هذا 0 مثلا هذه اربعه ايام وهنا سوف يقوم بكتابه النشاطات التي سوف يتم عملها طيب كما اتفقنا سوف يكون لدي المصفوفه اذا اي والمصفوفه دي بي واثنان اثنانهم سوف يكون عدد العواميد ثلاثه وعدد الاسطر سوف يكون حسب المستخدم كم سوف يدخل عدد الاسطر طيب الان ناتي الى كتابه الكود ففي البدايه كما اتفقنا انه سوف يكون لدي مصفوفه دي بي لماذا وضعت مثلا هنا 200000 لانه حسب ما اعرف الانبوت لسه من المستخدم ففرضت انا هذا الشيء الكولمز معروفه عندي سوف يكون لدي اما تايب صفر او واحد او اثنان كما اتفقنا طيب المصفوفه دي سوف ايضا يكون بها ثلاثه عوامل ايضا صفر وواحد واثنان كما اتفقنا بعد ذلك قامنا بانشاء داله هذه الداله التي سوف تستقبل ماذا ال عدد الايام والتايبز سوف يكون مثلا تايب صفر او تايب واحد او تايب اثنان طيب بعد ذلك في البدايه كما اتفقنا اننا سوف نقوم بانشاء مصفوفه هذه المصفوفه اسمها دي بي وسوف تحتوي على ناقص واحدات فقمت بانشاء فور قمت بانشاء مصفوفه الان هذا ما الذي قام بعمل هذا الكود قام بانشاء مصفوفه طولها طول كم عمود فيها ثلاثه صفر واحد اثنان كم سطر بها حسب المستخدم كم سطر سوف يقوم بالاستخدام فقمت بملئها كلها بايش بالناقص واحده بالشكل هذا بعد ذلك ما الذي الان سوف اقوم باخذ الان وهو عدد الايام لدي عدد الايام لدي مثلا كان يوجد لدي خمسه ايام بعد ان قمت باخذ عدد الايام الان لابد ان اخذ عدد ماذا؟ اقوم باخذ قيم النشاطات اللي عندي 100 50 دقيقه 40 دقيقه 30 دقيقه فايضا قمنا بانشاء المصفوفه دي هنا جاء دور المصفوفه دي التي سوف تكون كم سطر كم عمود ثلاثه صفر واحد اثنان كم سطر حسب مثلا الايام حسب الايام كما اتفقنا الايام والسطور عفوا العواميد والسطور ال السطور سوف تكون الايام مثلا لو ادخل ثلاثه فستوف تكون صفر واحد اثنان ثلاثه ايام كما صفر واحد اثان اليوم صفر اليوم واحد اليوم اثنان ويقوم ماذا بملء هذه القيم من المستخدم طيب ما الذي سوف يحدث بعد ذلك؟ الان ا نقوم ماذا؟ باخذ الماكس من ماذا؟ من الاحتمالات الثلاثه انا كم احتمال سوف ابدا عندي؟ سوف يكون لدي ثلاث احتمالات التايب صفر التايب واحد والتايب اثنين سوف مثلا ادرس مسار انه يمشي بهذا بالتايب صفر ومسار يمشي بالتايب واحد ومسار يمشي بالتايب اثنين فاخذتهم تايب التايب واحد التايب اثنين التايب واحد التايب صفر بعد ذلك راح اخذ الماكس من بينات وبعدين يقومون بالحساب وارجاع النتيجه من هذه الداله سوف اقوم باخذ ماذا؟ الماكس فيما بينهم سوف اقوم باخذ الماكس فيما بينهم طيب لماذا استاذ لماذا ان ناقص واحد لانه كما اتفقنا الايام سوف تدع من الصفر فصفر واحد اثنان فسوف تكون ثلاثه ايام مثلا اذا دخل مستخدم ال ان ثلاثه 3 - 1 2 فسوف يكون ثلاثه ايام طيب ناتي تي الان الى اين؟ الى كتابه الداله دائما دائما الخطوه الاولى في الداينامك بروجرامين اسمها البيس كيسز لابد كتابه البيس كيسز طيب ما هي البيس كيس لدينا عندما يكون الاي يساوي صفر ايش يعني الاي تساوي صفر لو كان لدي مثلا يوم واحد لو ادخل المستخدم يوم فالان 1 ناقص فسوف تصبح صفر فا هنا تحققت الحاله اي لدي يوم واحد هنا لا يوجد لدي الايام البقيه يوجد لدي يوم واحد فاليوم هذا سوف اختار الماكس فيما بينهم فماذا اي تايب فاما تايب اي تايب اثنان او تايب واحد او تايب صفر سوف اقوم باخذ الماكس فيما بينهم طيب بعد ذلك كما اتفقنا دائما الخطوه الثانيه ماذا يكون انني اتحقق هل قمت بحساب الدي بي هذا سابقا ام لا القيمه هذه التي سوف اقوم بحسابها هل تم حسابه قبل ام لا كما اتفقنا انه في مصفوفه الدي بي مليئه بالناقص واحدات فالان اول مره دخلت بال بالكود منهن اكيد لاني سوف يكون كلها ناقص واحدات فما الذي سوف اقوم بعمله سوف اقوم بالذهاب الى حساب ال شنو اسمه حساب مصفوفه الدي بي سوف ابدا ب مصفوفه الدي بي اذا كما اتفقنا يوجد لدي ثلاثه سيناريو السيناريو الاول لو كان ماذا التايب صفر الان سوف ادرس الحاله الاولى هذا هو التايب صفر التايب واحد التايب اثنان ماذا لو التايب صفر اذا اذا اختاريت مثلا التايب صفر لا استطيع ان اخذ تايب صفر النوب مره في اليوم التالي لابد ان اخذ 80 او 50 انا ابحث عن ماذا الاكبر كيف سوف احصل على الاكبر عن طريق داله ماكس ممتاز فالان سوف اقوم باخذ الماكس اما من الاثنان من التايب اثنان او من التايب واحد جميل من التايب اثنان او التايب واحد فالان اخذت ماذا الماكس فيما بينهم الان لابد ان ايش ان اقوم بجمع ماذا اقوم بجمع العدد اللي قبله مثلا هنا كم كانت باخذ نشاط قيمته 10 مثلا فلا بد ان اقوم باخذ النشاط اللي قيمته 10 بعدها الماكس من هنا كم سوف يكون مثلا 80 الماكس من هنا ثمانيه سوف اقوم يقوم باخذ ال 80 ويقوم بوضعها وين؟ ياتي الى الدي بي اي تايب مثلا التايب لديه صفر ف سوف يذهب الى الدي بي تايب ويقوم بوضع ماذا؟ الحاسبه التي قمنا بحسبها وهي 90 يقوم بوضعها في المكان المناسب كما اتفقنا مثلا هذه صفر واحد اثنان هذه داله الدي بي وقام بوضع ال 90 في المكان المناسب طيب الان هذه الحاله صفر الحاله صفر اللي هي التايب اي بعد ذلك الحاله الثانيه وهي ماذا لو كان التايب واحد ماذا لو كان التايب واحد ماذا لو كان التايب واحد ما الذي سوف يحدث سوف نفس الذي قمنا بعمله سابقا وانما سوف تختلف الخيارات اما اخذ صفر او اثنان اما اخذ من التايب صفر او عفوا من التايب صفر او التايب اثان نعم لانني اخذت من التايب ماذا؟ تايب واحد سابقا لاني اخذت من التايب يا اما هذه القيمه اما هذه القيمه طيب ماذا لدي؟ بقي لدي الخيار الاخير لو بدات من الاثنين ما الذي سوف يحدث لو بدات من الاثنين ما الذي سوف يحدث وهو الالص الاخير لابد ان اخذ من ماذا اما الصفر واما الواحد يا اما اخذ الصفر ويا اما اخذ الواحد اقوم بحسابه ايضا مال القيمه القديمه وين اتج اقوم بوضعها في الدي بي فالان عندما اقوم بالرجوع الى هنا اذا كان اورريدي محسوب فرجعه مباشره اذا كان مو محسوب ارجع احسبه احنا كما اتفقنا الدي بي سوف تكون مليئه بالناقص واحدات وكما ترون قمنا بملئها بعد ذلك كما قلنا سوف نقوم بملء مصفوفه الدي بي بالاعداد المناسبه وبعد ذلك سوف اقوم اقوم بارجاع الدي بي اي اوف تايب وهو الناتج بعد ذلك ما الذي سوف اقوم بعمله سوف اقوم بطب بطباعته على الشاشه سوف اقوم بطباعته على الشاشه اقوم بتشغيل البرنامج فالان مثلا لو فرضنا يطلب مني بالبدايه عدد ماذا؟ عدد الايام عدد الايام نفرض انه كم مشان ما يطول يفرض انه لديه ثلاثه ايام مثلا 10 40 نقوم بملها بعد ذلك 90 فماذا افضل خيار هو 210 وهو افضل خيار سوف يقوم بماذا؟ باخذه افضل خيار كان يوجد لدي ثلاثه ايام وسوف يقوم ويكون الناتج 210 كما رايتم هذا هو الكود يعني ربما يكون صعب في الوهله الاولى ولكن بعد الممارسه تجد انه امر سهل اي الداينامك بروجرامين دائما تستخدم في البدايه اعيد واذكر البيس كيس ثاني شيء يكون لدي الشرط البيس كيس طبعا يوجد حالات حسب الحالات يوجد بيس كيس واحده او يوجد اثنان حسب الحاله اللي عندي هذا المنطق الذي في الاسفل يتغير حسب منطقه السؤال حسب منطقه السؤال الناقص واحد دائما سوف اقوم بملء داله الدي بي 90% من الحالات بالناقص واحد الن معروفه وباقي ما تبقى امور سهله فهذه الخطوات الاساسيه لحل اي مشكله بالداامك بروجرامين اتمنى ان الدرس نال اعجابكم والسلام عليكم ورحمه الله وبركاته