AlgoDP
السلام عليكم ورحمه الله وبركاته يا رب تكونوا بخير جميعا يا شباب welcome back. محاضره النهارده ان شاء الله هي ثاني محاضره في ال dynamic programming, more examples على ال DB. احنا خدنا اخر محاضره فكرته ومثالين عليه والنهارده بنكمل more examples ان شاء الله. سريعا كده بعض ال announcements في الاول. بالنسبه لاخر مساله خدناها في المحاضره اللي فاتت هي ال rod cutting هستأذنكم هن check اخر 10 دقائق في ال video.
video ال uploaded على ال channel عشان نشوف تفاصيل step 5 اللي هي construct a solution. احنا كنا وقفنا في المحاضره لحد ازاي نرجع ال optimal value لكن ما عرفناش مين ال cuts اللي اديت optimal او اللي جابت ال optimal solution. ف step 5 في ال DB هي ان احنا ن construct a solution او نعرف مين الاختيارات اللي ادت للحل اللي احنا حصلنا عليه.
فهتلاقوا ده مشروح للمساله دي في اخر 10 دقائق في الفيديو اللي فات استاذنكم نبص عليها والنهارده ان شاء الله هن re-iterate على على الخطوه دي بس من خلال مساله ثانيه يعني. ان شاء الله assignment 3 اللي هو اخر assignment عندنا قبل المشروع قبل ال project هيبقى released ان شاء الله باذن الله خلال النهارده او بكره يعني باذن الله. هو عباره عن مساله على ال DB. كل واحد هيجي له النسخه بتاعته على ال CI a C mail بتاعه ومدتها تقريبا اسبوع لحد يوم الاثنين اللي جاي ان شاء الله.
وكالعاده ال submission بن submit الملف اللي فيه الحل اللي هو problem class.cs. ال evaluation عليها five marks يعني من ال total بتاع ال assignment mark. طبعا كالعاده هي زي ال assignment 2 برضو بيبقى في C sharp template based given مع حضراتكم. بيبقى في قراءه ال input و checking ال output و sample test cases زائد واحده one complete case.
والمطلوب ان احنا نت ال function الحل. ال sample test cases بتبقى صغيره هدفها ال ensure the correctness. دي بتبقى ال evaluation عليها one mark وال unseen large test cases بيبقى معاكم اوريدي one one seen test ولما تسلمه بن check احنا على ten unseen tests.
دي بيبقى هدفها ال efficiency وبالتالي بت test على ال large input. ودي طبعا اللي بيبقى الهدف الاكبر من فكره ال design عموما يعني ان هو احنا بن check بنشوف ال efficiency على large input. فارجو ان احنا نبتدي على طول عشان نلحق اذا كان في اي مشاكل او حاجه نتداركها في ال office hours ان شاء الله. ال announcement الاخيره بخصوص ال team المشروع يعني.
ال group registration هو المشروع هيبقى ان شاء الله باذن الله يعني هيبقى released خلال الاسبوع اللي جاي. من الاسبوع ده هنبتدي نسجل ال teams بتاعتنا. عدد ال members per group بيبقى من اربعه لسته members. ممكن من cross sections أو cross departments مفيش مشكله. التسجيل على الرابط ده لحد يوم الجمعه اللي جايه يعني لحد نهايه الاسبوع ده
ان شاء الله. ال form هت accept من اربعه لسته. لو في ناس ما عرفتش تكون teams اربعه ممكن تسجل اقل من كده وبيبقى بن handle ده في في الاخر في التقييم يعني ان شاء الله. to advice سريعا بخصوص المشروع.
work as a team. اتأكد ان ال team اللي انت بتختاره مش مهم العدد قد ما هو يكون فعلا team بيشتغل لان في الاخر ال requirements بتبقى على قد ال load يعني على قد assuming ان ان شغالين team يعني فبيبقى المطلوب على قد العدد اللي شغال خلال الفتره الزمنيه المخصصه للمشروع ان شاء الله. والنصيحه الثانيه ابتدي على طول.
ما ترحلش عشان تلحق يبقى عندك فرصه لفهم المساله، فهم المطلوب، لو في اي مشاكل او اسئله لو في ابتديت في ال implementation وعندك حاجه واقفه او bugs او كده تلحق تسال ونستغل ال office hours خلال الاسابيع اللي جايه ان شاء الله. نتمنى لكم التوفيق ان شاء الله ويا رب يكون مشروع ممتع يعني لحضراتكم ومفيد باذن الله.
ان شاء الله طيب  احنا بنتكلم على ثاني محاضره في ال dynamic. سريعا نـ review ال dynamic بسرعه كده نراجع هو كان ايه؟ هو عباره عن careful brute force بيجرب كل الحلول بس بياخد باله من التكرار. وبالتالي هو divide and conquer بكامل شروطه. divide بيقسم لمسالتين او اكتر, conquer بيحل كل مساله بنفس الطريقه وبيرجع يـ combine ال solutions. بس فرقه عن ال divide ان في overlap
subproblem مسائل بتتكرر. وبالتالي لو سبناه divide and conquer يعني top down من غير ما نحتفظ بالحلول كده هتلاقي ان المسائل بيتكرر الحل بتاعها redundantly بدون داعي وبالتالي بيؤدي الى complexity عاليه جدا بتبقى في الغالب exponential. فكان البديل وهو ده ال DP بقى ان احنا نحل نبتدي من ال base case اللي هو احنا اوريدي عارفين الحل بتاعه ونبقى نبتدي نحل.
كل أما نحل حاجة نخزنها في extra storage وبالتالي أما نحتاجها نرجع نجيبها يبقى كل مسألة اتحلت مرة واحدة فقط. طبعا هدف انه فعلا بي switch مسائل كتير من ان هي تبقى exponential الى تبقى polynomial وده بيخليها feasible ان هي تتحل او ت run على الكمبيوتر. بيستخدم في الغالب في مسائل ال optimization اما اللي هي بتدور على ال optimal solution اما يكون
في تفكيرنا العادي بتاعها ما بنعرفش نختار مين الحل الانسب. بنقول دايما محتاجين نجرب عندنا كذا option وما نعرفش مين ال option اللي هيجيب الحل افضل حل يعني الا لما نجربه. فما دام لو هي كده يبقى دي DB. اما لو لو احنا عارفين مين الحل مين ال option اللي هيؤدينا للحل ال optimal ساعتها ساعتها دي بتبقى greedy. ده الفرق ما بين الاتنين يعني.
خطوات الحل قلنا هم five steps. اول خطوتين هم يعتبروا 80% تقريبا من الحل اللي هو define the problem لان انت في الاخر هنحطها على شكل problem و subproblems فايه هي ال problem اصلا؟ ايه ال parameters وايه ال return بتاعها؟ الخطوه الثانيه وهي الاهم وهي ال most important step في الخطوات كلها هي ال divide and conquer solution اللي هو
ان احنا نعرف نجيب ال possibilities بتاعتنا ونجيب الحل ال recursive يعني. بعد كده بن check ال overlap لو في overlap يبقى هي هنكمل وتبقى محتاجه ان احنا نخزن الحلول. لو مفيش overlap يبقى هي اتحلت divide and conquer سواء بقى efficient او لا بس هي خلاص كده اتحلت مفيش داعي ان احنا نكمل. step 4 لو في overlap فاحنا بن switch واكدنا على فكره ال switch انها
فعليا systematic way بن switch بيها من ال divide and conquer الى ال DP سواء top down او bottom up. totally هي systematic steps. steps بنفذها او بنمشي عليها systematic ما فيهاش اي نوع من التفكير يعني. فلو احنا top down بنسيب ال recursive عادي ولو المساله not exist فبن calculate و save. اما لو كانت exist
يعني موجوده في ال previous records فبن retrieve المساله دي بن retrieve الحل. option 2 ان احنا نحلها bottom up وده بيبقى في الغالب بيبقى loop يعني بنسميه building table وده بيبقى عباره عن loops بنعمل بنحل فيها كل ال subproblems سواء احتجناها او لا. لحد step 4 ده بيجيب ال optimal value فقط وليس الحاجه اللي كونت اللي جابت ال optimal.
هو ال optimal value كقيمه, step 5 هو extract the solutions او الاختيارات اللي ادت الى ال optimal solution ده. بعد كده شوفنا تفاصيل step 2 هي طبعا هن iterate عليها مره ثانيه خلال المسائل النهارده ان شاء الله, بنجس ال subproblems, بن formulate كل subproblem بنحاول نجيب ال base case وبعدين بن relate. step 4 و step 5 الاثنين systematic way سواء ال step 4 سواء top down او bottom up.
كلها totally systematic way. حليناهم المره اللي فاتت وهن iterate عليهم برضو المره دي ان شاء الله من خلال المسائل اللي معانا. ال two approaches bottom up وال top down. ال bottom up بيحل كله سواء احتجناه او لا, ال top down بيحل بس اللي احنا محتاجينه عشان كده كان ال guideline ان احنا لو محتاجين لو المساله محتاجه ان هي تحل معظم او كل ال subproblems يبقى الاحسن
نمشيها bottom up. يعني ال bottom up بيتجنب ال recursion وال recursion overhead عاليه بسبب ال stack, ال calling stack والتعامل مع ال memory. اما لو معظم ال subproblems مش محتاجه تتحل فساعتها ال top down بيبقى افضل لان احنا بنحل فقط اللي احنا محتاجينه.
نيجي برضو لفكره اشكال ال subproblems خاصه اما بنتعامل مع strings او او sequences يعني. عندنا ثلاث اشكال مشهورين قوي في ال subproblems اما نيجي ن define subproblem لاي مساله شغاله على strings او sequences. يا اما prefixes. subproblems prefixes يعني دايما بتقل من الاول دايما بتصغر من الاول ومستمره دايما.
لحد الاخر فدائما بتقل من الاول. او العكس suffixes دايما بتصغر من الاخر ودائما بتوصل لواحد او زيرو فدائما هي بتقل من الاخر ف prefixes يعني دايما بتبقى المحتوى بتاعها ال prefix بتاع ال sequence. او substring من الى يعني بتقل بتصغر ال subproblem بتصغر من الاول ومن الاخر.
وبالتالي بناء على الثلاثه options دول نقدر ن estimate او نعرف عدد ال subproblems. لو احنا عندنا suffixes والمساله حجمها من واحد ل N يبقى احنا عندنا totally N possible subproblems من غير تكرار. كذلك ال prefixes عندنا N possible subproblems.
subproblems بدون تكرار. اما ال substring عشان هي بتقل من الاول ومن الاخر فعندنا total maximum N square possible subproblems. اللي هي من واحد لواحد من واحد لاتنين واحد لثلاثه لحد من واحد ل N بعدين من اتنين لاتنين اتنين لثلاثه اتنين لاربعه لحد اتنين ل N وهكذا وهكذا فده بيدينا total N square subproblems.
ده كان quick recap كده على محاضره اللي فاتت وعلى ال DB بشكل عام. عندنا النهارده ان شاء الله ثلاث امثله مختلفين بكل مساله بتكفر حاجه معينه او technique معين في ال DP. وعن وفي الاخر بن conclude ال DP مع extra questions موجوده بقى كالعاده في ال sheets وال
problem sessions وفي ست سبع محاضرات دي برضو optional examples موجوده بالشرح بتاعها وبالحل. ممكن ت consider دي على انها برضو extra problems ممكن تبص عليها وتشوف الحل بتاعها. هم three اتنين منهم هم good example ت practice ويعتبروا في نفس مستوى المسائل اللي احنا بنعملها targeting خلال ال course. واحده يمكن advanced شويه للي عايز ي challenge
نفسه اللي هي ال optimal binary search tree يعني دي ممكن advanced شويه اعلى شويه من مستوى ال course او اللي بناخده يعني في ال course بس يعني هي interesting problem وممكن الناس تبص عليها. هدف المحاضره طبعا ان احنا نطبق ال dynamic على على مسائل المناسبه ليها ونعرف امتى نختار ليه اخترنا ال dynamic وطبعا هي بتعتبر example على ال time space .
دي ال references, mainly يعني هي من other schools المسائل اللي عندنا اخترناها من references خارجيه فدي ال references بتاعتها للي عايز يبص على تفاصيل اكتر فيها. وبنفكر نفتكر دايما ان احنا لازم ن practice يعني تغيير طريقه التفكير جناحين جناح التعلم ال learning وجناح ال practicing لازم يمشوا مع بعض. فال learning بيتم من خلال المحاضره السيكشن اللاب
ال examples اللي احنا بنتعلمها مع بعض. اما ال practice فده بيتم بقى من خلال ال assignments من خلال ال sheets من خلال ال problem sessions فممكن كل دي مصادر او etc يعني اي حاجه ثانيه. المهم ان انت تمارس ده. تعالوا نخش على طول على اول مساله عندنا ان شاء الله اللي هي ال knapsack. ال knapsack يمكن اتعرضنا ليها قبل كده فكرتها سريعا شنطه ليها وزن maximum
capacity وعندنا شويه items كل item ليه وزن ليه سعر. والمطلوب ان احنا نملى الشنطه دي بال maximum total benefit يعني عايزين ن maximize ال benefit بتاعنا. المساله دي فيها variations كتير. واحده من ال variations بتاعتها اتعرضنا ليها ساعه ال greedy اللي هي ال fractional knapsack.
في عندنا بقى variations ثانيه هنتكلم عنها سريعا دلوقتي. ال variation الاولاني اسمه ال 0-1 knapsack ان كل item فيه منه only one instance فقط. فيا اما ال instance دي لو خدناها خلصت لو ما خدناهاش خلاص فضلت فهي في one instance من كل نسخه واحده من كل item. ودي اللي هنحلها مع بعض ان شاء الله.
في نسخه ثانيه بتبقى bounded يعني هي برضو كل كل item ليه عدد من ال instances بس مختلف يعني ال item ده ممكن يبقى فيه منه five instances, ال item الثاني ممكن يبقى فيه منه three, ده ممكن يبقى فيه منه seven, ده ممكن يبقى فيه منه two, ده ممكن يبقى فيه منه one وهكذا. ففي limited number of instances بس مش شرط واحد.
يعني من كل item. ال variation الثالث unbounded ان كل item فيه منه عدد لا نهائي من ال instances ودائما الهدف هو واحد عايزين ن maximize ال benefit. فنلاحظ ان هي مساله optimization اهي maximize يبقى احنا optimal optimization problem. بتستخدم في ايه الحقيقه؟ تطبيقاتها كتير يعني من اهمها موضوع اي تطبيق فيه لو احنا عايزين ن minimize ال waste of materials يعني.
عندنا مثلا container وعايزين نملاه بشويه items بحيث ن maximize ال عدد ال items اللي جوه او ن minimize ال waste of space, عندنا مثلا storage devices او storage DVDs وعايزين نملاهم ب content بحيث ن minimize ال total number of storage devices او storage
DVDs فكل دي تطبيقات يعني. كذلك ليها تطبيق في مجال تاني خالص في مجال ال cryptography اللي منكم هياخد ان شاء الله security او ماعرفش ولا لا في موضوع ال cryptography مساله مشهوره قوي اسمها subset sum دي برضو بتبقى بتخش كتير في موضوع التشفير وفك التشفير يعني. طيب خلينا ناخد المساله بتاعتنا اللي هي ال 0-1 knapsack كل item فيه منه نسخه واحده يا ناخدها يا ما ناخدهاش.
ما ناخدهاش. المساله دي طبعا عشان نحلها اتعرضنا ليها قبل كده ساعه ال brute force ما نعرفش نختار مين فاحنا محتاجين نجرب. فبالتالي كل item عندنا لو هم N items من واحد ل N فكل item قدامه two options يا اما ناخده يا ما ناخدوش. كل item ليه two options وبالتالي total ال options اللي عندنا two times two times two, N times يبقى احنا عندنا
total two power N options محتاجين نجربهم كلهم ونشوف مين منهم اللي ينفع ون maximize عليه. فبالتالي ال complexity هنا at least exponential, two power N. طبعا ده لو هي brute force. وبالتالي دي مستحيل انها تتحل على الكمبيوتر ايا كانت سرعته يعني. طيب خلينا ن switch بقى المساله نشوف هل هي فعلا هي طبعا واضح ان ه
فيها شروط ال dynamic او على الاقل الاستخدام من ناحيه الاستخدام هي هي مساله optimization اهي maximize وفيها ان احنا محتاجين ن try. يبقى احنا عايزين ن maximize والحل بتاعي الحل العادي بتاعها ان احنا محتاجين ن try.
solutions ما نعرفش نختار مين ما نعرفش ن pick انهي item في الاول محتاجين نجرب. وبالتالي هي محققه شروط او يعني القاعده بتاعت استخدام امتى نستخدم ال DB. هنركبها على شكل DB ف step 1 define the problem.
فلو احنا سمينا ال problem دي مثلا knapsack فيهمنا هنا ايه ال parameters وايه ال return ده المقصود ب define the problem هتاخد ايه تشتغل ايه ال parameters اللي هي تشتغل عليها وايه ال return اللي المفروض ترجعه؟ نبتدي بال return ال return معروف هو ال maximum total
total benefit اللي هي fill الشنطه اللي معانا ال knapsack اللي معانا. طب ايه بقى ال parameters نفسها؟ زي ما كده المحاضره اللي فاتت ودايما بناكد الموضوع define the problem ان اللي يهمنا في ال parameters هو ال parameter اللي بيمثل حجم المساله وليس اي وليس كل ال parameters يعني اكيد هنحتاج ال weight بتاع كل item اكيد هنحتاج
ال price بتاع كل item. كل دي okay parameters بس دي fixed parameters ما بتتغيرش. لكن اللي يهمنا في ال parameters هنا هي ال parameters اللي بتتغير اللي هتتغير وهتشكل حجم المساله. فواضح هنا ان طبعا في parameter واضح جدا اللي هو الشنطه نفسها وزن الشنطه. اللي هو W. فوزن الشنطه ده parameter صريح.
وده هيتغير كل شويه كل ما نحط item الوزن ده هيقل. فوزن الشنطه. زائد في parameter تاني اللي هو مين ال items اللي احنا حاليا بن select منها. initially احنا عندنا N items بن select منهم. بس ال N دول later on هيتغيروا هيقلوا.
لانه هي 0-1 knapsack فلو احنا قررنا ناخد item معين المره الجايه ال item ده مش معانا في الاختيارات. فبالتالي بن exclude ال item ده ونجرب بقيه ال items. عشان كده ال N اللي هو عدد ال items اللي احنا حاليا under consideration هو برضو parameter مهم يمثل حجم المساله.
بس مفيش parameters تانيه هنا مهمه فيبقى ده defining the problem. وبالتالي لما نيجي ننطقها لو جينا تعرف منين انت فعلا عملت ال problem صح؟ اما تيجي تنطقها تلاقيها فعلا بتمثل المساله اللي انت عايزها. فننطق كده ال knapsack دي احنا عايزين ن find ال maximum total benefit اللي هي fill
شنطه وزنها W, knapsack of weight W, using N items. يعني او considering N items. وبالتالي هو ده فعلا اللي احنا عايزينه. هنملى الشنطه دي من اصل ال N items اللي معانا من واحد ل N. بس تحت شرط ان احنا عايزين ن maximize.
ال total benefit. فكده عرفنا المساله. step 2 دي الاهم اتفقنا دي اللي تقريبا تمثل 80% يمكن من الحل, ال divide and conquer solution, ال recursive solution. step 1 فيه ان احنا نجس ايه هي ال possibilities ايه ال trials اللي عندنا؟ احنا قلنا ان ال DP او ال optimization بيستخدم في ال optimization
لما يكون عندنا trials طب ايه هي ال trials اللي عندنا بقى؟ ايه التجارب اللي عندنا؟ اما بنفكر فيها بنفكر فيها في اول مره بس يعني اقل مستوى نجرب بيه. فاقل حاجه نجرب بيها هنا هو single item صح؟ ال item اللي عليه الدور اللي حاليا under consideration. ايه ال options اللي بالنسبه اللي عندنا بالنسبه له؟ يا اما ناخد ال item ده
معانا. وبالتالي لو خدناه يبقى هو هيتسحب هيقل هيتحط في الشنطه وبالتالي وزن الشنطه المتبقي هيقل وهتبقى ال value بتاعته هتتضاف معانا. وساعتها هن maximize على الباقي على بقيه ال items وبقيه الشنطه. لان ال item ده خلاص اتاخد وبالتالي excluded.
او ان احنا ما ناخدش ال item. يعني ال item اللي عليه الدور مش قررنا ان احنا ما ناخدوش لان ممكن لو ما خدناوش وخدنا غيره يدينا حل افضل. فاحنا حاليا مش عارفين فمره هنجرب ناخده take ومره هنجرب نسيبه فطبعا لو سبناه يبقى احنا محتاجين ن maximize برضه المسألة.
بس المره دي هن maximize الشنطه هي هي لكن ال items هن exclude ال item اللي احنا كان under consideration بمزاجنا احنا اللي قررنا نسيبه ونجرب بقيه ال items. فدول ال two options اللي عندنا. طبعا في option تالت هنبقى او يعني في احنا مش دايما ال two options دول متاحين بالمناسبه. ما دول متاحين لو كان ينفع اصلا ناخد ال item.
يعني وزن ال item ي fit في وزن الشنطه. لكن لو مش هي fit احنا مجبرين ان احنا نسيبه. لو هو not fit, can not fit فاحنا مجبرين ان احنا نسيب ال item ده وبالتالي هي نفس نفس ال subproblem بتاعه ال leave يعني. كده عرفنا ال two options اللي عندنا, يا احنا عندنا two possible choices.
cases. step 2 في ال divide and conquer solution محتاجين نحول كل option منهم الى subproblem. ما هو الفكره ان احنا عايزين نحطه divide and conquer عايزين نعرف ال subproblems بتاعتنا. رايكم ال subproblems هنا انهي واحده من الثلاثه دول؟ ممكن الناس تشارك يعنى اتفضلوا
انهي واحده من الثلاثه؟ اول واحده؟ suffixes. ممكن تبقى suffixes وممكن تبقى prefixes ممتاز. ممكن الاتنين الحقيقه. ممكن تبقى suffixes وممكن تبقى prefixes.
لان احنا بالنسبه لنا ال items اللي هم ال N items هل هتفرق هنجرب اول item ولا اخر item؟ هل في ترتيب معين بنجرب بيه ال items؟ مفيش. فهي مش فارقه هنجرب انهي item, هنجرب الاولاني الاول ولا هنجرب الاخير الاول؟ مش فارقه.
احنا كده كده هنجربهم كلهم. فاذا هي تنفع suffixes وتنفع prefixes. يبقى احنا عايزين ن formulate بقى ال subproblems طبعا احنا اللي شغالين بيه حاليا هو prefixes لان احنا بتقل من الاخر. احنا ابتدينا ب N لو تفتكر احنا عرفنا ال problem على انها knapsack
of W و N يبقى احنا بادئين ان احنا باصين على كل ال items, ال N items كلهم. ايه بقى ال subproblems في حاله ال take وفي حاله ال leave؟ في حاله ال take هن maximize يعني هنادي على نفس ال نفس ال problem الاساسيه بس على اللي فاضل من الشنطه مع اللي فاضل من ال items. يعني
W minus وزن ال item اللي احنا اخترناه, و N minus 1 لان ال item خلاص excluded لان احنا قررنا ناخده. ده كده هيجيب لنا ال optimal solution على بقيه ال subproblem, بقيه المساله. بس ما تنساش ان انت اوريدي خدت ال item ده معاك. فيبقى ال value بتاعته ال price بتاعه اتضاف للحل.
اتضاف للمجموع ما تنساش ان انت عايز ال maximum total benefit. فال benefit بتاع ال item اللي انت اخترته هو بقى معاك زائد ال maximum بقى اللي هو احسن حل على بقيه ال items. ده في حاله ال take. طيب في حاله ال leave واضحه. still هن maximize على الشنطه كامله لان احنا ما حطيناش فيها حاجه لسه بس هن exclude ال item يعني N minus 1.
N minus 1. طيب ده هيجيب حل وده هيجيب حل. عايزين منهم ال maximum في الاخر. وفعليا احنا ما نعرفش مين اللي هيجيب maximum في ساعتها احنا لازم نجرب نحل ونرجع في المسالتين وبعدين نختار ال maximum. وبالتالي هنا بقت optimization وفيها تجارب. step 3 الbase case امتى نقف
امتى نقف هنا؟ امتى ال recursion يقف؟ لما اكون جربت كل ال items. اه يعني اما ال N وصلت صفر. ال items خلصت. او لو الشنطه نفسها اتملت. او لو الشنطه نفسها اتملت ممتاز اللي هو ال W وصل صفر. طيب ساعتها ال total benefit كام؟ ايه ال total benefit اللي يملى شنطه
وزنها صفر؟ المتبقي فيها صفر؟ صفر. طيب نفس الفكره. ايه ال total benefit اللي يملى شنطه فيها وزن بس مفيش items. ما عنديش items اختار منها. صفر برضو. صفر برضو. ف سواء الشنطه بقت صفر او ال items خلصت
في الحالتين مفيش benefit مش هعرف احط مش هعرف اكتب حاجه في ال subproblem دي فده ال base case.كده عرفنا ال subproblems عرفنا ال base case فاضل ان احنا ن relate كله ببعضه في recursive solution. simple خالص, ال knapsack اهي ال problem الاساسيه W و N. والله لو ال W بصفر او ال N بصفر برجع صفر. غير كده
عندي checking الاول هل الشنطه هل ال item اللي عليه الدور ينفع ي fit في الشنطه ولا لا؟ ال W of N وزنه اكبر من وزن الشنطه ولا لا؟ لو وزن ال item ما ينفعش ي fit يعني اكبر من وزن الشنطه ساعتها انا مجبر مجبرين ان احنا ن leave ال item ده. ده by force مش هينفع نجرب لان هو اصلا ما ينفعش ناخده. اما غير كده فاحنا محتاجين نجرب ال two options
ال take وال leave وهن maximize هنرجع ال maximum بين الاتنين. بس هم الثلاث سطور دول هم دول الحل بتاع المساله, ال divide and conquer solution بتاعها. دي تعتبر اهم خطوه زي ما اتفقنا في الحل. step 3 ال overlap. عشان نفهم ال overlap هنا
ممكن ناخد ارقام يعني يعرض لنا الصوره شويه. لو احنا عندنا دي ال weight بتاعه ال items ودي ال values. فعندنا لو ابتدينا ب item رقم اربعه. item رقم اربعه وزنه 15. فلو خدناه لو قررنا ناخده فال W هتقل ب 15. و N minus 1.
لو قررنا نسيبه هيفضل ال W زي ما هي. طيب next. الدور اللي مره الجايه سواء في ال problem دي او ال problem دي الدور على item رقم تلاته اللي هو وزنه 10. لو خدناه يبقى هنقل على ال 15 هنقل 10 كمان يبقى 25. ولو سبناه يبقى هيفضل 15 بس N - 2. نفس الفكره الناحيه الثانيه.
لو خدناه هتبقى W - 10 ولو سبناه هتبقى ال W هي هي و N - 2. لو عملنا مره كمان بالنسبه لل item رقم two وجربنا مره ثانيه وكتبنا ال subproblems هنلاقي ان ابتدى يظهر عندنا مسائل متكرره اهي. ال subproblem دي هي هي دي. وبالتالي بما ان ابتدى يظهر متكرر فده وارد انه يتكرر كل شويه.
التكرار ده هيضر وطبعا لان ما تنساش التكرار ده كمان انت بتكرر ال problem بكل ال sub-tree اللي تحتها. طبعا ال recurrence بتاعه المساله دي لو احنا اشتغلنا على ال N فقط يعني assuming ان ال N هنقف اما ال N هتخلص. كل مره بنزل فرعين يعني two T N - 1 وال complexity بلس بقيه ال code order one.
دي اما نحلها tree هتطلع ال complexity exponential يعني زيه زي ال brute force. وده متوقع لان انت بتجرب كله ووارد التكرار. وبالتالي ده ينقلنا الى step 4, ال switching. هنا بقى في المساله دي ال switching هنا هل هو top down افضل ولا bottom up؟ هنا السؤال ده الحقيقه بيبقى خاضع لطبيعه المساله
وطبيعه ال input اللي داخل. بس generally it seems هنا الاقرب ايه؟ bottom up ولا top down الافضل؟ top down. top down ممتاز. ليه top down؟ لو احنا فكرنا ايه ال possible subproblems اللي عندنا؟ احنا عندنا المساله knapsack في two parameters, W و N فانت عندك total عدد ال
subproblems W times N. السؤال بقى هل انت هل واحنا شغالين بنجرب كل ال subproblems دي؟ يعني اما كنا عند W و N هل جربنا كل ال column ده؟ هل حسبناه كله؟ اطلاقا احنا حسبنا فقط كنا عايزين W
و N اللي هي دي. طب ال column اللي قبله اما كانت N - 1 هل حسبنا عند N - 1 كل ال possible W's؟ من ال W دي مثلا ب 10000 هل جربنا عند N - 1 وواحد و N - 1 واتنين وتلاته واربعه وخمسه وسته لحد 10000؟ هل عملنا كده؟
هنا على على الاقل بصوا على المثال ده فعليا لا. لو تاخد بالكم احنا جربنا ايه؟ اما عند N - 1 جربنا عند N -1 و W اللي هي دي. وجربنا عند N - 1 و W مثلا - 15 و - 25 و - 10 و - 5 ممكن later on بس مفيش مثلا
- 3, - 4, - 6, - 7, - 20, - 11
 كل ده مش موجود. 12. فبالتالي انت هنا معظم ال subproblems مش محتاج تحلها. فاهمين الفكره؟ وبالتالي الافضل هنا هو ال top down بس
بس take care, take care ان ده factor برضو في نسبه ال subproblems اللي انت محتاج تحلها. انت ممكن ما تحتاجش تحلهم كلهم. بس ما انت لو احتجت مثلا تحل مثلا 90% منهم, 80% منهم احيانا بيبقى ال 90 او 80% من ال subproblems دول الاحسن ان انت تحلهم bottom up بيبقى اسرع من لو حليتهم top down رغم ان انت محتاج بس 80%.
أو 90% من الـ Subproblems ليه؟ بسبب ال overhead بتاع ال recursion. ال overhead بتاع ال recursion عالي جدا. كذلك ال data structure اللي انت بتستخدمها في ال storage. فهو ده بيعتمد على ال input كقاعده عامه لازم تاخد بالك من شكل ال input اللي عندك. بس generally المساله دي الافضل ليها top down لو احنا فعلا نسبه ال subproblems كانت قليله جدا بالنسبه لل total.بة الـ Subproblems كانت قليلة جداً بالنسبة للـ Total
هنشوف مثال على كده. طب تعالوا ن switch مع بعض top down. طبعا في الحالتين سواء top down او bottom up لازم ن define ال extra storage وقلنا ان في قاعده عامه هنا ان عدد ال dimensions لو هي array يعني عدد dimensions هو عدد ال parameters اللي بتتغير. فاحنا عندنا two parameters يبقى احنا محتاجين two dimensional array, W في N. او لو عايز تعملها hash table
هتعمل hash ب composite key بقى او hash of a hash يعني عشان عندك two dimensional parameters او two dimensional storage يعني. طيب ده step 1 لو قررنا ان هي array يبقى لازم ت initialize ال array دي ب null. null يعني value
cannot be calculated during the solution. رايكم هنا ايه ال possible value لل null هنا في المساله دي؟ negative اي رقم negative, zero ينفع؟ لا لان ال zero هو مش هحصل حاجه طبعا لان ال zero هو احد الحلول خلي بالكم. ال zero هو ال base case.
فهنا لو انت هتخليها array يبقى الافضل انت ت initialize ب negative value. step 3 سيب ال code ال recursive عادي بس زود سطرين. سطر بتاع ال retrieve والسطر بتاع ال save. لو هي مش موجوده لو هي ب null يعني مش موجوده امشي recursive عادي خالص زي ال code اللي قدامنا ده.
بس قبل ما ت return القيمه خزنها في ال storage وبعدين رجعها, solve and save. اما لو هي موجوده اوريدي يعني مش ب null يعني موجوده ف retrieve ال value وما تكملش ال recursion اقطع ال recursion وكمل وما تكملش الحل يعني ما تكملش الحل ورجع لي القيمه خلاص ما هي already موجوده.
وبالتالي بتسبها كده top down وبتفضل هي بقى تحل نفسها لحد اما يرجع لك الحل الكبير بتاع المساله اللي هو W و N وهو ده اللي انت في الاخر عايزه اللي هو knapsack of W and N. نيجي لل code قلنا بنحتاج زي ما ال note اللي هي موجوده فوق يمين هنا بنحتاج three steps, واحد  ال extra storage وعرفناها اهي.
ان هي initially ب -1 او لو هي hash table يبقى initially فاضي. الحاجه الثانيه ال retrieving لو ال storage القيمه اللي في ال storage مش ب null يعني موجوده already يبقى احنا بن retrieve يبقى لو هي موجوده في ال memo بتاعنا retrieve القيمه دي رجعها. ودي ثاني حاجه بنعملها.
الحاجه الثالثه بنسيب ال code ال recursion عادي خالص زي ما هو بالظبط وفي الاخر خالص قبل ما نرجع القيمه سواء كان ينفع ناخدها او ما ينفعش قبل ما نرجعها اللي هي ال M دي بنخزنها في ال storage عشان المره الجايه نلاقيها. وطبعا كذلك نفس الموضوع في ال base case. فاحنا هنرجع صفر خزنه الاول وبعدين
فنرجعه. ده الفكره يعني, store وبعدين retrieve. بس كده. فدول ال three steps اللي بنعملهم عشان ن switch من top down من divide الى memoized solution واعتقد ده يعتبر الاسهل في التحويل لان هو نفس ال code اللي عملناه من شويه زودنا عليه ثلاث سطور فقط. وده الاسهل في التحويل وهو الانسب هنا. نيجي لل complexity.
هل ده خاضع لل recursion؟ يعني لقوانين ال recursion؟ لا. ليه؟ لان هو بيقطع الشجره الشجره ما بتكملش لحد الاخر بسبب خطوه ال retrieve. وبالتالي ده مش خاضع لل recursion ما ينفعش نعمله بال master او بال recursion tree whatever لا ليه قاعده ثانيه قلناها الاسبوع اللي فات اللي هو عدد ال subproblems في ال complexity per one.
طيب احنا عندنا هنا اجمالي كم كم كم subproblem distinct يعني من غير تكرار؟ كم واحده يا شباب؟ كم distinct subproblem هنا؟ قلناها من شويه واتحظنا برضو. N في W. N في W ممتاز, N في W. طب والواحده بتكلف قد ايه؟
اختار اى واحدة منهم O of 1. O of 1 لان هي سواء موجوده هترجعها يبقى O of 1, base case هترجعها O of 1, هنا او هنا بت maximize على قيمه او بترجع قيمه ففي الاخر كل ده order 1 يبقى هي W في N في order 1 يعني ال complexity بتاعتنا W في N.
W في N على الحل اللي احنا قلناه دلوقتي. اللي هو موجود قدامنا على الشاشه. الحل ده theta ولا O؟ وليه؟ هو ممكن يبقى O لان ممكن ماعديش على كل ال subproblems.
هو احنا اصلا اخترنا ده فعلا عشان ما نعديش على كل ال subproblems ممتاز. فالمفروض ان هو يبقى O. بس الحل اللي قدامنا ده اللي قدامنا عشان كده قلنا اللي قدامنا على الشاشه ده. احنا ده الحقيقه انه theta مش O. ليه بقى؟ حد يعرف؟ لو كنا في المحاضره كنا ادينا bonus يعني
حد يعرف؟ اه عشان ال array نفسها لما هاجي اعملها initialize. ممتاز برافو عشان الخطوه دي عشان اما ت initialize ال 2D array ب negative هتتلفك order W في N اللي هو حجم ال array. فاهمين الفكره؟
ورغم كده ده هتلاقيه برضو ممكن يبقى على حسب طبعا نسبه ال subproblems بس ممكن ده برضو يبقى اسرع يعني. فبالتالي دي ال complexity بتاعتنا هي فعليا theta على على بتاعنا ده بس المفترض ان هي لو استخدمنا data structure ثانيه غير ال array يعني dictionary او hash table كانت هتبقى upper bound W في N. ده ينفع نقول عليه polynomial؟
لا شفناه الاسبوع اللي فات ان ده بنسميه pseudo-polynomial شبيه ال polynomial ما ينفعش نقول عليه N square يعني. لان ال W مش هي ال N. ال N عدد items وال W يمثل وزن الشنطه. فده غير ده ما ينفعش نقول ان هي N square فبنسيبها W في N. لان الوزن غير عدد ال items. وده بيتسمى ساعتها pseudo-polynomial. جاوبنا على السؤال ده هل محتاجين نحل كل ال subproblems؟ الاجابه لا.
طيب على حسب النسبه بقى انهي الافضل لو كان نسبه ال subproblems قليله؟ مين الانسب هنا ك data structure hash table ولا array؟ طبعا يعني اعتقد الافضل لو النسبه قليله قوي الافضل ان انت تستخدم hash table يعني. وده مثال يوضح لنا الفرق بين الحلين على مثال صغير كده سريعا.
نشوف قد ايه الفرق بين الاتنين ده طبعا على حسب ال input اللي given. هنا ده مثال على
شنطه وزنها N million وعندنا ال seven items دول او ال eight items دول. eight items ودي الاوزان والاسعار. فتلاحظ هنا الاوزان multiple of thousand يعني الاوزان مش مش واحد اتنين تلاته لا ده المسافات ما بين كل وزن والتاني كبير قوي.
والشنطه كذلك وزنها كبير جدا. فلو احنا جربنا المساله دي top down اديتنا حل و bottom up عطلت شويه والمفروض هتدينا نفس الحل. بس نشوف بقى فرق الوقت ده الوقت بتاع ال top down ده الوقت بتاع ال bottom up. النسبه تقريبا حوالي 335 مره ابطأ
ال bottom up عن ال top down ليه؟ لان لو بصينا على ال subproblems اللي نسبه ال subproblems من اصل 100 مليون subproblem تقريبا من اصل 100 مليون subproblem اللي اتحسب منهم حوالي 430. فبالتالي كان ال top down اكيد افضل حتى لو هو ب hash table عن
ال bottom up طلع ابطا بحوالي 335 مره يعني. بس طبعا زي ما اتفقنا ده factor في عدد ال subproblems اللي بتتحل. بس ده كان حاجه للتوضيح يعني. 
طيب نيجي ل extract the solutions ودي الخطوه يمكن اللي ما تكلمناش عنها المره اللي فاتت بس يعني موجوده في ال video بتاع المره المحاضره اللي فاتت وكذلك يعني خلينا نشوفها مع بعض المحاضره.
عشان ن extract the solution. هو ايه extract the solution؟ ايه المقصود ب extract the solution؟ ان احنا احنا لو تاخدوا بالكم ال subproblem اللي فاتت المساله اللي وصلنا فيها ل step 4 احنا في الاخر رجعنا ال total benefit كرقم وليس ال items اللي اخترناها يعني في الاخر
اللي راجع ده هو ال value ال maximum total benefit بس مش مش الايه؟ مش ال items نفسها ما نعرفش مين ال items اللي اخترناها. ف extract the solutions مطلوب مننا نعرف مين بقى الاختيارات اللي عملناها كل مره. فبرضو دي systematic step يعني ليها standard طريقه كده في الحل طبعا ممكن ت optimize عليها في بعض المسائل لكن خلينا ناخد ال standard اللي هو ينفع مع اي مساله.
هما خطوتين, بتعرف storage ثانيه قد ال storage الاصليه بت save فيها ال best choice اللي عملته في كل مره. مش احنا كان كل subproblem كان قدامنا اختيارين يا take, take or leave وكنا بعد اما جربنا عرفنا مين الافضل اللي هو مين ال maximum واخترناه؟ ال extra storage دي هدفها تخزن ال choice نفسه بقى, ايه الاختيار اللي انت
اختارته في ال subproblem دي. الكلام ده على كل ال subproblems اللي انت مريت عليها عشان كده بنعرف storage ثانيه قد ال storage الاصليه. step 2 او step 1 طبعا من خزن بقى الاختيارات يعني هنا اما كان وزن ال item اكبر من وزن الشنطه اضطرينا ن leave اللي هو N minus 1 ونفس ال W. خزن علامه ت indicate ان انت
option ال leave يعني حرف ال L مثلا سهم بالجنب whatever يعني. المهم خزن علامه ت indicate ان الاختيار في ال subproblem دي كان هو اختيار ال leave. else بقى else كان عندنا two options يا اما ال take لو كان هو الاكبر يا اما ال leave لو كان هو الاكبر. فايهما اكبر خزن علامه تدل عليه في ال storage الجديده.
لو كان ال leave هو الاكبر خزن نفس العلامه, لو كان ال take هو الاكبر خزن علامه ثانيه. ايه لازمه العلامات دي؟ اللي بت indicate الاختيارات عشان في step 2 بقى هتباك track على ال solutions بتاعتك. هتبتدي من لو انت عندك لو تفتكروا احنا كان ال problems عندنا W
في N فكان الحل بتاعنا موجود عند W N اللي هي اللي هنا. هتبتدي ت backtrack من هنا. من الحل الاخير. تبتدي تشوف هو الحل ده مين اللي جابه؟ فبت pass I و J و check عند I و J طبعا في الاول بت passها ب N W N
W N ده في الأول خالص بس generally لو هي I و J. بت backtrack بقى لو هي كان الاختيار اللي عند I و J كان السهم اللي بالجنب معناها ان ده كان اختيار ال leave. كان هو الافضل سواء كنت مجبر عليه او كان هو الافضل ساعتها. مش فارقه معاك هي سواء ده او ده انت في الاخر
الاتجاه اللي انت جيت منه هو الاتجاه ده. فبت backtrack عند نفس ال W بس N minus 1 اللي هي I و J minus 1 اهي عشان انت كنت جايبها من هنا او من هنا اهو I و
 J - 1. هو طبعا هنا معلش دى مش I و   J  معلش هبقا اعدل دى فى ال
دي المفروض الـ I هنا هي مفيش I و J هي W وهنا N كل الـ I و الـ J دول هما W و N لان هما ال parameters اللي احنا شغالين عليها يعني W و N هنعدل ده بقى في النسخة الrelease ان شاء الله دكتور فى delay جامد في الصورة
في delay جامد في الصوت. مش الصوت, في الصورة. الصورة. اه هي طب انتوا حاليا ايه؟ يعني دلوقتي ايه؟ لسه بيكتب؟ يعني انا انا سامع حضرتك هو الكتابه لسه خلصانه من من حوالي خمس ثواني مثلا او ثانيتين. اه اه معلش بقى في الغالب تقريبا مشكله انترنت بس يعني للاسف ما
انا عملت switch لل network يعني ما عنديش option ثانيه يعني. تمام تمام شكرا. طيب معلش يعني اتمنى ان شاء الله يتحسن يعني. طيب عموما يعني كنا بنتكلم على ال backtrack يعني ف فاحنا هنبتدي I و J اللي هم W و N. والله لو الاختيار كان سهم بالجنب يبقى احنا كده leave فبن backtrack على I و J - 1
اما لو كان السهم اللي هو بالورب ده فكان الاختيار ده جاي من فين؟ من I - W of J و J - 1 اللي هو ده. اللي هو ده I او اللي هو يعني W - W of J و J - 1 باعتبار ان احنا هنا على حسب انت مباصي parameter I و J ولا W و N.
انهي واحد فيهم اللي احنا قررنا ناخده فيه هو الاختيار الثاني الاختيار الاولاني دي الاختيار الثاني هو ال take. يبقى فين ال item اللي احنا اخترناه؟ هو اللي في الاختيار ده. فبالتالي بنروح طابعين ال item بقى على حسب عايز تطبع رقمه عايز تطبع قيمته وزنه خلاص انت عرفت ان
الاختيار ده لو دخلت في ال else دي هو ده الاختيار بتاع ال take. طب حد يعرف ليه طبعناه بعد ال recursion مش قبل ال recursion؟ خلي بالكم ان ده ده recursion يعني بن backtrack يعني بن recurse على نفس ال function يعني بنفضل ماشيين بقى كده كده كده كده لحد اما نخبط
في base case اللي هو ال I بصفر او ال G بصفر خلاص بن return ساعتها ونوقف ال backtrack. علشان نطبعهم بالترتيب نطبعهم بالظبط لان احنا بادئين من الاخر الاول فاحنا عايزين نطبعهم بترتيبهم الصح من الاول للاخر. ده طبعا هي مش فارقه طبعتهم في من الاخر للاول او من الاول للاخر مش هتفرق. في المساله دي طبعا بالتحديد يعني. بس ده كان تفاصيل ال extract the solution
ده التحويل بتاع ال building table هسيبوا لحضراتكم ك self study تبصوا عليه برضو كأفكار إزاي تحول من code divide إلى dynamic building table إحنا جربناه كثير السبوع اللي فات وحنجربه تاني النهاردة برضو بس يعني هو ده موجود على المسألة دي لو حابب تبص عليه طبعا بيدي نفس ال complexity نيجي بقى ل example على greedy لو اقترضنا مثال مثلا عندنا
الشنطه وزنها خمسه وعندنا اربعه items دي اوزانهم واسعارهم الوزن والسعر دول الاربعه items اللي عندنا. وبالتالي لو احنا عايزين نعملها table, building table يعني هي طبعا مش فارقه هتحلها top down او bottom up بس يعني الاقرب في ال trace الاسهل ت trace في انك تعملها building table.
فتعالوا نعملها building table. بنعرف storage W في N بس هي actually W+1 في N+1 عشان احنا عندنا ال zero base case. فمن 0 لخمسه ده عشان الشنطه وزنها خمسه ومن 0 لاربعه عشان احنا عندنا اربعه items.
الbase case عندنا هو ايه؟ لو ده بصفر او ده بصفر صح؟ فلو صفره اي حاجة دايماً حيبقى الحل بصفر اي حاجة وصفر برضه الحل بكامل بصفر نيجي بقى للcell دي واحد وواحد
يعني ايه واحد واحد؟ يعني شنطه وزنها واحد وحاليا انت باصص على ال item رقم واحد. ال item رقم واحد وزنه كام؟ اتنين. ينفع تاخده؟ في الشنطه اللي وزنها واحد؟ لا. ما ينفعش. ايوة اتفضل لا كنت بقول لا اه لا تمام
تمام هى الشنطة وزنها 1 و ال item اللى عليه الدور وزنه 2 فانا مجبر ان احنا نسيبه يعني هنخش في ال else دي اللي هي ال leave. مجبر ان انت تسيبه. طب اما بتسيبه بتروح لانهي؟ بتروح لل cell اللي هي عند I و J - 1. او يعني نفس الوزن
بس معلش احنا عكسين اهو يعني خلينا ده G مش مشكله عشان نبقى ماشيين نفس ال. ده ال I وده ال G خلاص؟ يبقى I و G - 1 اللي هي ال cell دي. عشان كده كنا بنحط سهم بالورب بالجنب لو تفتكروا. سهم بالجنب معناه ان انا باخد I, I و G minus 1 اللي هي دي. او I - 1 و W او I و G - 1.
القيمه هنا بكام؟ بصفر وانا مجبر ان انا اسيب leave يعني ما زودتش حاجه. طيب ال cell اللي بعدها, الشنطه وزنها واحد والدور على ال item رقم اتنين, ال item رقم اتنين وزنه تلاته. والشنطه وزنها واحد برضه مش هينفع ناخده يبقى مجبر ان احنا نسيب leave يعني هناخد القيمه اللي هنا الصفر.
نفس الفكرة برضو بالنسبة للـ item ده، وزنه أربعة، مجبر إن احنا نسيبه لإن الشنطة وزنها واحد، وكذلك الـ item الأخير برضو مجبر إن احنا نسيبه. طب ده بالنسبة للـ row ده. الـ row اللي بعده الـ w باثنين. طيب، الـ item اللي عليه الدور دلوقتي هو الـ item ده وزنه اثنين، والشنطة وزنها اثنين.
فاذا ينفع ناخده صح؟ ينفع ناخده. فهنجرب. هنخش في ال option ده. مين الاكبر؟ اخده ولا ما اخدهوش؟ لو ما اخدتهوش يبقى احنا بنبص على ال cell دي. اللي هي ال leave. اللي هي I و J - 1. طب ولو خدناه؟
هو هو مفيش غير two options يا اما I J - 1 او I - وزن ال item اللي عليه الدور وبرضو J - 1. ف I و J -  1 اهي اللي هي ال cell بصفر. طب و I - وزنه؟ I اللي هي باتنين ووزنه باتنين يبقى 2 - 2
اللي هي zero. و j - 1، احنا حاليًا الـ j بواحد، واحد - واحد اللي هي zero. يعني الـ cell zero zero اللي هي الـ cell دي. الله، الاثنين زي بعض. لا، خلي بالك بقى. أنت في حالة الـ leave بتسيبه وخلاص، لكن في حالة الـ take بتاخده، يعني بتزود قيمته على اللي موجود في الـ cell.
لأن أنت خدته، قررت تاخده. فيبقى أنت لو خدته قيمة الـ item ده هو وزنه اثنين وقيمته ثلاثة، يبقى أنت فعلًا خدت قيمته، يبقى ثلاثة زائد zero أحسن من الـ zero، أكبر يعني. يبقى الحل هنا إن أنت تاخده فعلًا.
ويبقى القيمة بثلاثة. اللي ما عرفش دي، نجرب واحدة ثانية. اثنين، الـ cell اللي بعدها اثنين والـ item الثاني، الـ item رقم اثنين. الـ item رقم اثنين وزنه ثلاثة والشنطة وزنها اثنين. ما ينفعش آخده أصلًا، يبقى أنا مجبر إني أسيبه اللي هي الـ else. فمجبر إن أنا آخد ده.
ما عنديش options. نفس الفكرة، اللي بعده وزنه أربعة واللي بعده وزنه خمسة برضه مش هينفع آخدهم. فباخد، مجبر إني أسيب، يعني باخد القيمة اللي في الـ cell اللي جنبي. اللي هو ده أحسن حل عندي حتى الآن. نيجي للي بعده. شنطة وزنها ثلاثة، والـ item وزنه، الـ item الأولاني وزنه اثنين، ينفع آخده، فيا إما أقرر.
أقرر أسيبه، اللي هي الـ cell دي، أو أقرر آخده يعني الـ cell اللي واقف عليها اللي هي ثلاثة - وزنه اللي هو اثنين، يعني واحد. و i و j - 1 اللي هي zero. يعني الـ cell واحد و zero اللي هي دي.
وأجمع عليها قيمته اللي هي ثلاثة. يبقى3 + 0 بثلاثة أحسن من الـ 0. يبقى الأحسن هنا ثلاثة والحل جاي من فوق. طيب، الـ cell اللي بعدها، الـ item اللي بعده دلوقتي وزنه ثلاثة وسعره أربعة والشنطة اللي عليها الدور وزنها ثلاثة اللي احنا بنحل عندها دلوقتي، يبقى ينفع آخده.
لو قررت أسيبه يبقى ببص على الـ cell دي. لو قررت آخده يبقى هقول الـ i اللي واقف عليها اللي هي ثلاثة minus وزنه اللي هو ثلاثة، يعني صفر. و j minus 1 اللي هي الـ j حاليًا باثنين ناقص واحد.
يعني بواحد. يعني الـ cell صفر وواحد، اللي هي الـ cell دي. بس ما تنساش الـ cell دي هتجمع عليها أربعة. يبقى صفر زائد أربعة ولا ثلاثة؟ الأكبر صفر زائد أربعة، يبقى الحل هنا أربعة وجاي من الورب، من السهم، من القيمة اللي فوق، من الـ take يعني مش من الـ leave. وهكذا، هكمل بقى بسرعة بعد إذنكم الباقي يعني.
طبعًا هنا الـ item ده وزنه أربعة والشنطة وزنها ثلاثة مش هينفع آخده، يبقى مجبر leave. وده برضه مجبرين نـ leave. Next، هنا برضه هتبقى ما بين دي وما بين دي زائد ثلاثة، فالأفضل إن احنا ناخذ ثلاثة والسهم بالورب. هنا برضه ما بين دي وما بين.
دي زائد أربعة. صفر زائد أربعة أو ثلاثة، فالأفضل هي أربعة بالورب. هنا الـ item ده ينفع آخده دلوقتي لإن وزنه أربعة والشنطة وزنها أربعة. فيا إما أسيبه أربعة، يا إما آخده اللي هو أما تحسبوها بقى هتلاقوها الـ cell دي زائد خمسة.
فالأفضل هي الخمسة جاية من فوق. هنا مجبر أسيب. بعد كده هنا نفس الفكرة، ثلاثة. هنا هيبقى ما بين... الشنطة هنا وزنها خمسة، فما بين الـ leave اللي هي دي، وما بين الـ take اللي هي دي +4 . 3+4 سبعة.
أحسن من الثلاثة، فالحل هنا سبعة بالورب. هنا نفس الفكرة، يا إما leave اللي هي السبعة، يا إما take اللي هي الصفر + الخمسة. 0 + 5 بخمسة، أو سبعة، فالأفضل السبعة، وإن أنا leave.
وبعدين الأخيرة هنا برضو ما بين leave أو take اللي هي 5 - 5  اللي هي دي، لإن الـ item ده وزنه خمسة وسعره ستة، فينفع تاخده. فإما 0 + 6 يا إما الـ leave اللي هي السبعة، فالأفضل هي السبعة.
هنا. لاحظ إن الحل الأخير، أفضل حل هنا هي السبعة. فعلًا الشنطة دي لما نيجي نبص عليها لو أنت عايز تملى شنطة وزنها خمسة من مجموعة الـ items دي، أحسن حل إن أنت تاخد الـ item الأولاني والثاني، اللي هما اثنين وثلاثة وزنهم خمسة، قيمتهم 3 + 4  7 .
يعني تاخد الـ item الأولاني والـ item الثاني، فده يسحب وزن اثنين وده يسحب وزن ثلاثة، كده خمسة، وال total benefit ثلاثة وأربعة سبعة، فعلًا أحسن حل السبعة. بس ما جابلناش الـ items. طيب، عشان نجيب بقى الـ items، بنـ backtrack.
دي هي نفس الحل، بس فصلت الأسهم عن الحل، يعني دي الـ matrix اللي كان فيها الأسهم ودي الـ matrix اللي فيها الحل. هنبتدي من السبعة، نـ backtrack. ها، backtrack كده من السبعة، السبعة كنت، كان أحسن حل إن أنت تـ leave. خلاص، امشي ورا الـ leave. امشي وراها، يعني روح للـ cell اللي جنبها وأنت هنا leave.
مش take. طب اللي وراها كان برضو الحل الأفضل هو الـ leave. يبقى امشي ورا السهم، يبقى leave. يبقى أنت سبت الـ item الرابع وسبت الـ item الثالث. عند الـ cell دي كان الحل الأفضل هو الـ take. طيب، هتـ take الـ item ده، يبقى الـ item ده معاك، okay؟ هتطبعه، ده معاك خلاص، صح. طب وأما تيجي تـ backtrack، بتـ backtrack بكام بقى؟
ما تنساش i - وزن الـ item و j - 1، أهو ده الـ backtrack. فـ i هنا اللي هي خمسة، ووزن الـ item اللي هو الـ item رقم اثنين ده وزنه ثلاثة.5 - 3  ب2 . والـ j حاليًا احنا واقفين على j باثنين، ناقص واحد يبقى.
واحد، يبقى هنروح للـ cell اثنين وواحد، اللي هي الـ cell دي، الـ cell دي. يبقى هنـ backtrack على الـ cell دي. هنـ recurse على الـ cell دي. طيب الـ cell دي جاية من فين؟ بص على الحل بتاعها، كان إيه أحسن حل هنا هو الـ take برضو. يبقى هتروح واخد الـ item ده معاك وتـ backtrack ثاني، هتلاقيها راحت على الـ cell رقم zero zero.
اللي هي الـ stopping condition، هترجع بقى تطبع ده وتطبع ده. فعلًا طبعت الـ two items اللي هما واحد واثنين. حد عنده سؤال يا شباب في الـ...؟ حد عنده سؤال؟
الـ complexity بتاعة الـ backtrack ده order كام؟ الـ upper bound ليها يعني order كام؟ worst case. n.
n إن هي تمشي كده، تفضل تمشي كده. ده n. آه أو w، إن هي تفضل تمشي بالورب، يعني كده أهو، كده أهو، تمشي واحدة واحدة كل شوية. فهي يا إما n أو w.
n أو w على حسب الكبير. ده كان، المسألة دي بكامل تفاصيل الـ five steps بتوع الـ DP.
خلينا ناخذ break خمس دقايق ونرجع إن شاء الله نكمل مسألتين التانيين اللي فاضلين في المحاضرة إن شاء الله. يعني مش هنكملهم طبعًا لحد الآخر بس يعني خلينا نـ break، نفصل شوية ونرجع تاني إن شاء الله.
نكمل. المسألة الثانية اللي عندنا اسمها text justification. المسألة دي برضو من المسائل المشهورة يعني، هي عشان نعرف يعني إيه المقصود بالـ text justification دي. عارفين أنتوا في، في أي text editor.
مثلًا زي الـ word. حاجة زي كده، أما يكون عندنا text زي كده، وبنيجي نـ select الـ text ده ونقوله justify.
justify إن هو يخليه دايمًا بادي من أول سطر وناهي عند نهاية السطر، لو كان ينفع طبعًا ينتهي عند نهاية السطر يعني. فحاجة زي كده مثلًا أهي، حتى لو خلينا مثلًا كده أهو. آه، ده كده مش مش justified. أما نيجي نقوله select كده و justify، تلاقيه إن هو خلاه كله بيبتدي.
بادي عند أول السطر وناهي عند نهاية الصفحة يعني. فده المقصود بـ text justification. طيب فالمسألة دي given الـ text على إنه list of words، مجموعة كلمات ورا بعض، المفروض يتحطوا بالترتيب ده يعني. ده الـ input بتاعنا، طبعًا الكلمات بـ different lengths. ومعاك عرض الصفحة اللي المفروض تـ fit فيها من أولها لآخرها، عرضها كام character.
وفي حاجة بيسموها الـ badness measure، مقياس قد إيه هو الـ justification ده سيء. المقياس ده ليه معادلات كتير، ممكن يتحسب بأكتر من معادلة يعني، بس المعادلة اللي احنا under consideration هنا، واللي هي اتطبقت فعلًا في الـ Word، هي عبارة عن عرض الصفحة ناقص الـ actual length.
الـ length بتاع الـ words من word رقم i لـ word رقم j، أما تيجي تحسب bad من i لـ j معناها من word رقم i إلى word رقم j. فلو أنت خدت من word رقم i لـ word رقم j وحطيتهم في السطر ده، دول ليهم length، اطرح الـ length بتاعه من length عرض الصفحة وارفعه power 3، cubic. بحيث إن أي فرق، أي مسافة زيادة.
أي space زيادة هتزودها تكلفك badness أكتر يعني، cubic badness. ده الكلام ده لو كان طبعًا ينفع يـ fit الكاركتر، الـ words اللي هي من i لـ j، ينفع تـ fit أصلًا في عرض الصفحة. أما لو كان not fitted، يعني الـ badness من i لـ j، الكلمات من i لـ j ما ينفعش أصلًا تتحط على عرض الصفحة اللي هو الـ page width.
يبقى ساعتها الـ badness بـ infinity، يعني أصلًا ما ينفعش تحطهم. كل ده given، يعني أنت معاك الـ input بتاع المسألة هو الثلاث حاجات دول. طب إيه المطلوب بقى؟ المطلوب هو إن احنا نـ split الـ text ده إلى good lines. يعني إيه good lines؟ يعني أولًا كلها تبتدي من أول السطر، من أول الصفحة وتنتهي في نهاية الصفحة.
ويبقى الـ spaces اللي بنزودها في النص minimized. نضمن إزاي إن هي minimized؟ إن احنا نحسب الـ badness لكل سطر. يعني مثلًا السطر الأولاني أنت خدت فيه الكلمات من واحد لثلاثة يبقى الـ badness كان من واحد لثلاثة مثلًا. بعد كده الثاني خدت من أربعة لسبعة يبقى الـ badness من أربعة لسبعة، وهكذا وهكذا. بحيث التوتال badness يبقى minimized.
يبقى أنت عايز تـ split الـ text ده إلى set of lines. كل line أما تحسب له الـ badness بتاعته وتجمع الـ badnesses دي، يبقى الـ total بتاعهم minimized. فاحنا عايزين نـ minimize الـ total badness بتاع السطور كلها. فهنا تلاحظوا إن هي مسألة optimization. Minimize أهي، مسألة optimization.
السؤال دلوقتي، هل هي greedy ولا dynamic؟ يعني بمعنى آخر، أول سطر، لو أنت هتبتدي طبعًا بأول سطر، تحط فيه أنهي كلمات؟ طبعًا أنت مجبر تبتدي بأول كلمة، ما هو لازم الكلمات تتحط بنفس الترتيب، يعني نفس الـ order ده. طب هتحط فيه أنهي كلمات بقى؟
تحط إيه اللي تحطه في أول سطر بحيث تضمن إنه يـ minimize الـ total badness بتاع السطور كلها؟ حد يعرف؟ طب الأول هو، حد عنده مشكلة في، في السؤال نفسه؟ يعني السؤال مثلًا لو حد عنده حاجة مش...
مش فاهمها يسأل يعني في المطلوب أو في الـ given. طيب، كله تمام. طيب سؤال بقى، نحط مين اللي نحطه في أول سطر؟ هل تعرف ولا ما تعرفش؟
قولوا أفكار، ما حدش يتكسف يعني، أي فكرة في بالك قولها يعني، أو في بالك قولوها وناقشها. في حد كاتب حاجة في الشات.
هو صعب أبص على الشات. طيب ماشي. أكبر عدد كلمات ينفع يتحط في السطر. جميل، لو احنا اخترنا أكبر عدد كلمات في السطر هل كده تبقى greedy ولا dynamic؟
أي حد يجاوب يعني مش... هتكون greedy. أربع عدد كلمات متتالية، كده بقت greedy. حلو جدًا، ممتاز. وده واضح إن الفكرة دي seems إن هي كويسة. بس خد بالك بقى من حاجة، أنت أما تختار أكبر عدد كلمات يـ fit في أول سطر، كده أنت عملت optimal.
لأول سطر، صح؟ جبت أقل badness لأول سطر. السؤال بقى، هل ده يضمن لك أقل badness في السطر اللي وراه واللي وراه واللي وراه، يعني بحيث يبقى الـ total badness minimized؟ هل يضمن ولا ما تضمنش إن هي minimize الـ total، بالظبط آه. ما يضمنش. ليه بقى ما يضمنش؟ لإن أنت ممكن.
في حالة ثانية مثلًا، ممكن يبقى فيه تستغنى عن كلمة هنا مثلًا. مثلًا الكلمة دي، ممكن تستغنى عنها ما تحطهاش في السطر ده، في line 2، تنزلها في line 3. يعني تنزل تبقى في بداية line 3. فتقلل الـ gap اللي هنا، فيبقى الـ total gap اللي أنت سبتها يعني، طبعًا assuming إن هنا
يعني الكلمة دي أكبر شوية والكلمة دي أكبر شوية، يبقى الـ total gap اللي نتج في السطر، آه السطر الثاني ما كانش أفضل حاجة للسطر الثاني فقط، بس أما خدته بقى استغنيت عن كلمة من السطر الثاني وحطيتها في السطر الثالث قلل لي الـ gap اللي في السطر الثالث وبالتالي قلل الـ total badnesses وبالتالي إداني أحسن حل. فاهمين الفكرة؟ يبقى احنا هنا إذًا.
فعليًا الـ greedy solution هنا هو هيـ minimize الـ badness بتاع السطر الأولاني فقط. وطبعًا أنت هتشتغل على كل سطر بنفس الطريقة أكيد، بس أنت ما تضمنش بعد كده إن أما تاخد أنت مثلًا أول مجموعة كلمات في أول سطر، ما تضمنش إن الكلمات اللي وراها، ما أنت لازم تحطهم بالترتيب.
هيحصلهم fitting في ثاني سطر بأقل badness. زي ما حصل كده في السطر رقم ثلاثة، شايفين السطر رقم ثلاثة؟ في gap كبيرة هنا نتجت بسبب ممكن الـ greedy choice. آه، يبقى احنا هنا ما تنفعش تبقى greedy. طب البديل إن أنت تجرب. طيب، لو هنجرب هنا وهنشتغل dynamic، أنهي option من الثلاثة؟
هنا اللي ينفع معانا؟ Substring. Substring. هل نفكر فيها، هل وإحنا بنحط الـ subproblem، أما بتيجي تحط الكلمات يعني، هل أنت بتحط من الأول ومن الآخر؟ آه لأ، بناخد من الأول بس. بتاخد من الأول بس، صح، يعني.
طيب، هل أما بتيجي تحط السطور بتحطها من السطر الأولاني للأخير ولا من الأخير للأولاني؟ من الأول للأخير. صح، لازم تظبط الأولاني وبعدين الثاني وبعدين الثالث، صح؟ آه يبقى إذًا كده هي مش مش substring، وهي بتظبط السطور.
من السطر رقم واحد إلى الأخير، وبالتالي يبقى هي دايمًا بتقل من الأول. يعني دايمًا الكلمات، هاخد شوية كلمات أحطهم في أول سطر يبقى معايا بقية الكلمات على بقية السطور. يعني لازم أظبط أول سطر الأول، فاهمين الفكرة؟ يبقى هي كده السيناريو بتاع المسألة دي هي.
مش prefixes ولا substring، هي suffixes. طب تعالوا نـ define الـ problem. text justification. text justification. إيه الـ parameters وإيه الـ return؟ هنا السؤال، احنا عايزين، عايزين نعمل إيه هنا؟
إحنا عايزين نـ minimize الـ total badnesses بتاع السطور كلها. طيب، إيه الـ parameters بقى اللي عندنا؟ الكلمات. الكلمات، بالظبط. طبعًا هو في parameters كتير، في الـ page width.
وفي الـ badness measure، وفي الكلمات، طول كل كلمة، كل دي parameters، okay ما اختلفناش. بس مين الـ parameter اللي أنا هشتغل عليه فعلًا ويمثل حجم المسألة؟ هي الكلمات بالظبط، هي الكلمات. طيب، أنت قررت تشتغل suffixes ولا prefixes؟ Suffixes. يبقى أما تحط parameter هنا تحط الـ parameter بتاع.
index الكلمة، لإن أنت مش هتبتدي بـ n، صح؟ أنت هتبتدي في الـ main، هتقول أنت عايز text justification ابتداءً من الكلمة رقم كام؟ i plus 1. one. الكلمة، يعني في الـ main أقصد، الـ main problem بتاعتك.
أنت عايز تـ justify السطور كلها، آه ابتداءً من أول كلمة، صح؟ يبقى i هو الـ index بتاع الكلمة، الـ word index، اللي هو يبتدي بواحد وبعدين يبقى باثنين وبثلاثة وبأربعة وبخمسة، كل شوية بيزيد يعني. ودايمًا أنت أما تشيل لحد الآخر، يعني هتخلص إمتى؟ أما الـ i توصل n، أو تعدي الـ n لو أنت 1-based، يعني تخلص الـ n كلمات كلهم.
يبقى كده خلصوا. ما فيش parameters ثانية هنا، parameters ينفع أشتغل عليها يعني، ثانية مش محتاج. رقم السطر، ممكن واحد يفكر في رقم السطر. بس خلي بالك إن أنت في كل مرة أنت هتدور على احسن حاجة ايه أقل unit تشتغل عليها هنا؟ الـ unit، أقل unit بتشتغل عليها.
أو هتـ optimize عليها سطر. فأنت أصلًا أما هتجرب، هتجرب على مستوى سطر. يعني فالمرة الجاية أنت عارف إن المرة الجاية أنت عايز تـ justify ابتداءً من السطر اللي وراه. لإن ما فيش حاجة أقل من سطر، يعني أنت لازم هتدور على الـ optimal، التجارب اللي تـ fit في سطر، أول سطر. المرة الجاية تشتغل من ثاني سطر.
لكن ما فيش inside السطر نفسه مش، ما فيش تجارب يعني، فاهمين الفكرة؟ يعني أقل unit بتجرب بيها هي إن أنت تـ fit في سطر يعني. فهي بس كده، text justification، أهو، minimize الـ total badnesses اللي تـ justify الكلمات اللي عندك ابتداءً من الكلمة رقم i، where إن i دي هي الـ word index.
index. نيجي بقى لأهم خطوة عندنا اللي هي الـ divide and conquer solution. إيه التجارب اللي عندنا؟ لو أنت مبدئيًا أهو عندك n، عرض الصفحة أهو، وعندك الكلمات موجودة بالترتيب. إيه التجارب، الـ trials اللي تعملها على أقل مستوى، اللي هو مستوى السطر الأولاني؟ إيه اللي تحطه في السطر الأولاني؟
ها، إيه اللي تحطه في أول سطر؟ حد يعرف؟ التجارب يعني. آخد كام كلمة؟ تاخد كام كلمة بالظبط. هل، هل option إن أنت تاخد كل الكلمات اللي بالترتيب اللي يـ fit في السطر هو ده الأحسن حل؟ هل أنت ضامن إن ده أحسن حل؟ لأ.
لأ، يبقى أنت محتاج تجرب. طب إيه بقى التجارب؟ والله ممكن أحط كلمة واحدة بس وأنهي السطر على الكلمة دي، ممكن تكون كلمة كبيرة. ممكن أحط كلمتين وأنهي السطر بعد الكلمتين دول. ممكن أحط أول 3 كلمات وأنهي السطر بعد الثلاث كلمات دول. ممكن أحط بعد أربع كلمات، خمس كلمات.
وأفضل أجرب كده لحد أما كل اللي ينفع يتحط في السطر ده. السؤال بقى، هل أنت عارف أنهي option من دول اللي هيديك قدام أما تخلص minimum total badness؟ تعرف ولا ما تعرفش؟ لأ، لازم أجرب لكله برضه وبعد كده لكل احتمال من دول. بالظبط. فأنت فعليًا من الاحتمالات دي أنت مش عارف.
مش عارف مين منهم اللي هيديك أحسن حل، وكذلك اللي بعده، السطر اللي بعده، هتضطر تجرب فيه. فأنت محتاج تجرب كل مرة. طبعًا اتفقنا إن بنفكر فيها أول مرة بس. يبقى دول التجارب. كام تجربة هنا maximum، worst case؟ عندك كام تجربة؟
كام trials؟ بعدد الكلمات اللي ينفع تتحط في السطر ده، worst case إن هم يبقوا n، الكلمات كلها ينفع تتحط في السطر، يعني ممكن أجربهم كلهم، صح؟ أو إن أنت يعني، يعني ممكن توقف بدري عن كده لو أنت عارف فين آخر، بعد الكلمة رقم كام مش هينفع تحط في السطر ده، فممكن يبقى أقل من n يعني. بس يعني، لو احنا بنتكلم generally.
maximum هم n احتمال. دول الاحتمالات اللي عندنا. طيب، عايزين بقى نحول كل احتمال إلى subproblem. هي إيه الـ problem ما تنسوش، text justification starting من الـ index رقم i. طيب، لو أنت قررت تنهي أول سطر بعد أول كلمة، يبقى المرة الجاية عايز تـ justify من الكلمة رقم كام؟
2. 2، عايز أحسن حل يديك السطور من ثاني سطر للآخر ابتداءً من الكلمة رقم 2، أهو اللي هي i+1 يعني. ده لو أنت قررت تنهي بعد الكلمة الأولى، أو بعد يعني، بعد i، يعني خدت i وهتـ justify starting من i+1.
زائد ما تنساش، أنت قررت تحط الكلمة دي بس في السطر، يبقى الـ badness بتاعك هو الـ page width ناقص المسافة، ناقص طول الكلمة دي، اللي هو ده الـ badness، يعني ده الإضافة اللي أنت اضطريت تضيفها. ده اللي هو الـ extra spaces يعني.
يبقى هو ده الـ badness بتاعك. فبتحسب الـ badness من i لـ i. طب ده لو هو بعد أول كلمة، طب لو لو أنت كنت خدت كلمتين مش كلمة، يعني starting من i، خدت i وi+1، يبقى هتـ justify من الكلمة اللي بعدهم، من ثالث كلمة بعدهم اللي هي i+2. وهيبقى الـ badness بتاعك من i لـ i+1.
يعني أنت خدت الكلمتين دول فقط. يبقى هتطرح عرض الصفحة ناقص طول الكلمتين دول يديك المسافة دي، هي دي الـ badness، هترفعها power 3 يديك الـ badness بتاع السطر ده. تجمعه على بقية المسألة. وهكذا، لو بعد ثالث كلمة يبقى text justification of i+3 زائد badness من i لحد i+2، and so on.
من كل دول احنا عايزين إيه بقى؟ minimum. فهنحسبهم كلهم وبعدين نـ minimize. طبعًا كل واحدة منهم قلبت على subproblem أهي، subproblem. طيب، الـ base case، حد يعرف إمتى هنقف؟ لما ما يكونش باقي كلمات. بالظبط، احنا بادئين من واحد وهما n كلمة.
لما ما يكونش عندي كلمات، يعني ما أوصل لـ n+1. إيه الـ justification؟ إيه الـ badness؟ إيه اللي هتخسره لو أنت ما عندكش كلمات؟ مش هخسر حاجة، ما فيش كلمات أصلًا. يبقى الـ badness بكام؟ بصفر. فاهمينها؟ يعني مش هخسر حاجة، ما فيش، ما فيش badness أصلًا، ما فيش كلمات، فأنت مش هتحط حاجة في السطر.
ما فيش subproblem، مش كلمات، خلاص. نـ relate بقى كله ببعضه، يبقى text justification of i، لو الـ i بـ n+1، ده base case برجع صفر. وما تنساش إن الـ main بتاعك بادي من كام؟ من واحد. غير كده بقى هتـ minimize، هتجرب. هتـ minimize، الـ m initially بـ infinity وهتـ minimize على الـ m دي.
كل مرة ابتداءً من i+1 لحد n+1، كل مرة هتـ minimize المعادلة دي، اللي هي text justification of j، اللي هي بادية من i+1، زائد badness من i لحد j-1. عشان لو تفتكروا أهو، أما كنا هنا بعد أول كلمة، قلنا إيه؟ i+1 اللي هي الـ j، وبعدين من i لـ i، اللي هي يعني من i لحد.
j-1. هنا كانت i+2 أو اللي هي، اللي هي الـ j برضه، لإن الـ j كل مرة بتزيد. وهنا من i لحد i+1، الـ i+1 دي اللي هي تعتبر j-1. فدايمًا بتـ minimize على text justification of j اللي هي بادية من i+1 لحد n+1، وزائد badness من i لحد j.
j-1. في loop وفي الآخر بتـ return الـ m دي، الـ minimum فيهم كلهم. ده كده الخطوة الأهم اللي هي الـ divide and conquer solution. نيجي للسؤال رقم step 3، هل في overlap؟ يعني أعتقد واضحة جدًا، أنت أما تيجي تكتب text justification of 1، إيه التجارب اللي عند 1؟
1 2 و 3 و 4 و 5 لحدn+1. طيب، إيه التجارب اللي عند اثنين؟ ثلاثة لغاية n+1. ثلاثة وأربعة وخمسة. بالظبط، 3 4 . وعند 3، 4 5 6 . فهي مليانة overlapping يعني، كلها overlap. وبالتالي واضح جدًا إن هنا الـ dynamic هو.
choice هنا أهو، candidate choice. لو سبناها هنا هتطلع exponential برضه، 2 power n. البديل إن احنا نـ switch، top down ولا bottom up؟ وليه؟ bottom up. ليه؟ عشان احنا هنحتاج في الغالب نجرب كل الخيارات بتاعتنا. بالظبط، ده أنت من أول مرة تقريبًا بتجرب كله، وكل مرة هتجرب كله يعني.
فأنت بتجرب كله فعليًا، وهتجرب كل الـ subproblems وبتتكرر كمان، فبالتالي الأفضل إن أنت تمشيها bottom up عشان تتجنب الـ recursion. هنسيب الـ top down self-study لو عايز تبص عليه، ونحل احنا bottom up. Extra storage القاعدة بتاعتنا حجمها بعدد الـ dimensions. عدد الـ dimensions بتاعتها بعدد الـ varying parameters. أنت الـ parameter في كام واحد؟
one parameter، يبقى أنت 1D array حجمها n، بادية من واحد لحد n+1. ليه، ليه من واحد؟ ليه مش من 0 لـ n يعني؟ عشان لازم أختار كلمة واحدة على الأقل. آه، طب وليه n+1؟
مين n+1؟ مين الـ cell اللي في n+1 دي؟ آخر كلمة. الـ base case ولا؟ لأ ممتاز، لأ مش آخر كلمة، ده الـ base case. ممتاز برافو، ده الـ base case. ما تنساش إن احنا شغالين suffixes، فأنت بتقل دايمًا من الأول.
فأنت آخرك الـ base case إمتى؟ أما الـ i توصل n+1، تمام؟ طيب، الـ step 2، المعادلة اللي هنملى بيها أهي، بنجيبها من الـ code زي ما اتفقنا المحاضرة اللي فاتت، ما فيش جديد. أهي، لو الـ i بـ n+1 حط صفر اللي هي الـ cell دي. غير كده احسب لي في loop من i+1.
واحد لـ n+1 احسب لي المعادلة، القيمة دي. طبعًا القيمة بتـ retrieve array of j زائد badness من i لحد j-1، وبتجيب الـ minimum وتحطه عند الـ cell اللي أنت بتحسب عندها. جبت الكلام ده من فين؟ أهو من السطرين دول. الخطوة الثالثة، اكتب loop.
تملى الـ array دي. الـ loop دي تبتدي من فين؟ هو ده اسمه bottom up. يعني إيه bottom؟ مين bottom؟ bottom اللي هو إيه؟ الـ base case. الـ base case. يبقى الـ loop دي هتبتدي من كام؟ من n أو n+1. ممتاز، من n+1، من n+1.
لإن هو ده الـ base case. أهو، تبتدي من n+1 أنا عارفه فهحطه. بعد كده هنقل على n. الـ n محتاجة مين؟ محتاجة اللي بعدها اللي هي n+1، هعرف أحسبها. n-1 محتاجة الاثنين اللي بعدهم، هعرف أحسبها. وهكذا وهكذا لحد أما أوصل لـ array of 1. طب مين الـ solution الأخير اللي أنا بدور عليه؟ عند كام؟ الـ main problem كانت عند كام؟
قلناها، الـ main، آه الـ main أنت بتنادي الـ text justification عند كام؟ واحد. يبقى اللي أنت بتدور عليه هو ده، عكس المسائل اللي فاتت لو خدتوا بالكم، ده اللي بندور عليه لإن هي suffixes. بس، نكتب الـ code. أدي الـ loop من n+1 down to 1.
أملى الـ array من الآخر للأول، وتـ check الـ two conditions، يعني حط ده جوه الـ loop، حط الـ if then else دي جوه الـ loop. if الـ i equal n+1، خزن صفر. else، minimize، امشي بـ loop على الـ j من i+1 لـ n+1، minimize على الـ value دي اللي هي R of j زائد badness of i.
j-1. دور على الـ minimum، خلص الـ loop، هات الـ minimum ده وخزنه في الـ cell اللي عند R of i اللي أنت بتحسب عندها دلوقتي. ده لو كانت مش base case. Complexity. طبعًا في الآخر بـ return R of 1، ما تنساش.
طبعًا واضحة قوي الـ complexity هنا، دول loops, two loops، صح؟ عدد الـ iterations في الـ body، الـ loop اللي برة ماشية n، واللي جوه آخرها برضه n، بتمشي من n وn-1 وn-2 وn-3، أو يعني أو واحد واثنين وثلاثة وأربعة وخمسة لحد n. فالتوتال بتاع الـ two loops دول يطلع n square.
يبقى الـ code ده الـ complexity بتاعته n square. عدد الكلمات square. عشان كده لو هو على مستوى برجراف، البرجراف آخره كام يعني، 1000 كلمة؟ ما يوصلش حتى 1000. عشان كده بتبقى يعني efficient، can be calculated يعني 1000 square مليون وممكن تـ optimize عن كده كمان. فهي عشان كده موجودة، وبالمناسبة الـ greedy solution ده كان موجود في الـ Word بتاع Microsoft لحد تقريبًا 2007 يعني قبل.
2007 كانوا شغالين بالـ greedy. بعدين من ابتداءً من 2000 مش فاكر 2007 ولا 2010 يعني غيروه إلى dynamic. وفعلاً أما تقارن الـ justification بتاع الـ two versions دول اللي عنده يعني، هتلاقي في فرق ملحوظ بين الاثنين. نيجي لـ extract solution، ده هسيبه لكم بقى self-study. هم الخطوتين هم هم، هتطبقهم أنت على الـ code ده عشان تجيب.
تملأ الـ best split اللي عملته لكل subproblem، وبعدين تـ backtrack عليها. هسيب لكم ده، اعتبره إن ده مسألة في امتحان، أو يعني مش لازم امتحان يعني، بس اعتبرها مسألة ليك أنت لو أنت given الـ code ده إزاي تـ backtrack عليه. هي في الآخر systematic steps ما فيهاش تفكير، التفكير كله خلص في step 2. تمام؟
دي كانت المسألة الثانية، أرجو تكون وضحت لحضراتكم يا شباب. نختم أو في أي سؤال الأول؟ لو حد عنده سؤال يتفضل على طول يعني، لو حد ليه أسئلة.
طيب نختم بمسألة ظريفة، هي هي لعبة خلاص، بيسموها alternating coin game. نشرح المسألة واللعبة وبعدين نلعبها وبعدين نشوف الحل، خلاص؟ إن شاء الله. المسألة دي بيقول لي given n coins، صف كده من العملات، كل عملة ليها value وهما عددهم n، والـ n ده even دايمًا.
رقم زوجي. ومفروض إن في two players بيلعبوا قصاد بعض. كل player أما بيلعب بيختار يا إما أول عملة على الشمال أو آخر عملة على اليمين، يعني الشمال أو اليمين، أول عملة أو آخر عملة. وبعدين يختار، بعد أما يختارها يشيلها ويضيف القيمة بتاعتها ليه، يعني ياخدها معاه يعني.
بقت العملة دي معايا، خلاص؟ واللي في الآخر اللي هيكسب هو اللي هيجمع أكتر عملات. اللي هيكسب هو اللي هيجمع أكتر عملات. إيه المطلوب؟ المطلوب إن أنت تـ maximize المكسب بتاعك assuming إن أنت اللي بتلعب الأول.
مطلوب إن أنت تـ maximize المكسب بتاعك assuming إن أنت اللي بتلعب الأول. طبعًا واضح إن هي maximization أهي، maximize. خدتوا بالكم إن مسائل النهاردة كلها maximization أو optimization يعني، خلاص؟ بس قبل ما نفكر في المطلوب ده، خلينا ناخد مثال بأرقام ونخلينا نلعب يعني.
عايز اثنين متطوعين ممكن يـ raise hand يلعبوا اللعبة دي معانا الأول. طيب، هناخد مين، هناخد أول بقى اثنين، حسام عبد الرحمن وعبد الرحمن علي، خلاص؟ معلش هي بس عشان اللعبة هنا.
يعني ممكن تقولوا لي أنتم، هنبتدي حسام اللي هيبتدي خلاص؟ وبعدين عبد الرحمن، وهتقولوا لي كل واحد يقول لي الاختيار بتاعه، خلاص؟ أدي اللعبة أهي، player 1 حسام. هاخد اليمين. حسام، وplayer 2 عبد الرحمن.
حسام خد اليمين، حسام اللي ابتدى خد الستة، حسام خدت الستة صح؟ أيوة. تمام. هنشطب لحسام على الستة. أنا هاخد الـ19. عبد الرحمن كده قدامه يا 14 يا 19، فعبد الرحمن اختار .
الـ19. اختيار حسام. وبعدين عبد الرحمن اختار 19. ماشي. حسام. هاخد الـ22. حسام قدامه 14 و22، خد الـ22.
هاخد الـ14. عبد الرحمن خد الـ14. ما فضلش الـ36 واختار الـ14. كده كده هختارهم هم الاثنين. أيوه بالظبط. حسام. مش فارقة. 42. مش فارقة. هتختار 42. هختار 36، ما فيش غيرها. بالظبط.
ده الـ base case يعتبر بالنسبة لنا. مين اللي كسب في الآخر؟ هو أعتقد. حسام هو اللي كسب، total 70. عبد الرحمن اختار المجموع بتاعه كان 9
يا فرق واحد! فرق واحد بالظبط. شكرًا ليكم يا شباب. اللي كسب هو في الآخر player 1. السؤال بقى، ينفع حسام كان يكسب دايمًا، assuming إن هو player 1؟ أو أنا أسأل حسام، حسام أنت اخترت الستة randomly ولا كنت في بالك حاجة معينة؟
لأ ما قلتش أختار الـ14 عشان ما ياخدش هو الـ42. آه، بصيت لقدام شوية. طيب، السؤال بقى، ينفع أيًا كانت الأرقام اللي given، ينفع، ينفع نخلي player 1 دايمًا يكسب؟ ولا لأ؟
لو هيختار الأول يعني. أيوة، إيه؟ لو هيختار الأول ممكن يكون عنده فرصة أكبر. ما السؤال بيقول، ينفع الأولاني دايمًا يبقى هو اللي بيكسب أيًا كانت الأرقام؟ هي بتعتمد على اختيارات الثاني والأولاني الاثنين سوا. آه.
هو يا إما يكسب يا يتعادل، ما يخسرش. آه، ينفع؟ وإزاي؟ هو تقريبًا... ما تنساش إن أرقام even، آه، العدد، عددهم دايمًا even. أيوة، اتفضل. هو تقريبًا يعني يمكن يعرف النتيجة لكن مش دايمًا يكسب.
يعرف النتيجة مسبقًا بس مش دايمًا يكسب وهو اللي بيلعب أول واحد؟ طيب، ماشي، هقول لكم، معلش عشان بس وقت المحاضرة ما أعطلكمش أكتر من كده. بصوا يا شباب، الفكرة ببساطة هتـ check.
الـ even indices مجموعهم كام، وهتـ check الـ odd indices مجموعهم كام. والمجموع الأكبر تبتدي من عنده. ليه بقى؟ لإن الـ player 1 ده لو هو اختار...
الستة، لو ابتدى من هنا يعني، player 1 لو هو ابتدى من هنا، هو أيًا كان اللي قصاده هيلعب إيه، هو مجبر إنه يختار الحاجات اللي متعلمة بالأخضر اللي هي الـ even indices. مجبر عليها، أيًا كانت اختيارات الثاني. ليه بقى؟ لإن فكر فيها كده، هو أما حسام اختار الستة.
عبد الرحمن كان قدامه إيه؟ يا الـ14 يا الـ19، صح؟ أيًا كان لو اختار الـ14 أو الـ19، مين الأولاني؟ حسام، حسام كان يقدر يختار الـ next even، صح؟ يعني لو عبد الرحمن كان اختار الـ14، حسام كان يقدر يختار الـ42.
ولو عبد الرحمن اللي هو player 2 كان اختار الـ19، صح؟ لو هو كان اختار 19، كان يقدر player 1 اللي هو حسام يختار الـ22، يعني يقدر حسام يختار الـ even indices اللي هو عارف مجموعها من الأول، يقدر يختارها.
أيًا كان الـ player الثاني بيلعب إيه، فاهمين الفكرة؟ أيوة. وهو خلي بالكم، هو كان عارف مجموعها من الأول، فهو يقدر يكسب دايمًا. لو لقى إن مجموع دول اللي بالأخضر مجموعهم 70 واللي بالأزرق مجموعهم 69، يبقى هو كان المفروض حسام، أو player 1، يبتدي من الستة ما يبتديش من الـ14. طب لو كان العكس، كان المفروض يبتدي من الـ14 ما يبتديش من
الستة، وأيًا كان الثاني هيلعب إيه، هو يقدر يختار اللي في باله اللي هم سواء الـ even دايمًا أو الـ odd دايمًا. طب ده، ده معلش ده بعيدًا بقى عن هدف المسألة خلي بالك. هو السؤال ده بيقول إيه، ينفع player 1 يكسب دايمًا؟ آه ينفع بالطريقة دي. لكن المسألة عايزة إيه بقى؟ هي عايزة إن أنت تـ maximize.
المكسب بتاعك، مش بس تكسب، تـ maximize المكسب assuming إن أنت اللي بتلعب الأول. وخلي بالك إن في نفس الوقت اللي قدامك بيلعب maximum، بيلعب optimal برضه. يعني أنت عايز تكسب وتـ maximize المكسب assuming إن اللي قدامك بيلعب optimal. يعني player two أو اللي هو الكمبيوتر بقى قدامك بيلعب برضه.
الفرق بس إن أنت اللي لعبت الأول. فالسؤال دلوقتي، على المسألة دي، الـ given ده، تعرف تختار مين ولا ما تعرفش؟ Player 1 تعرف تختار إيه ولا ما يعرفش؟ أيوة آه.
كل مرة. كل مرة لأ. لإن أنت خلي بالك اللي قدامك بيلعب optimal. طب مش هو كده كده أصلًا يعني الحاجات اللي هو اختارها فهي كده كده أصلًا maximum وهي دي اللي هتكسبه؟ هي دي اللي هتكسبه، بالظبط، هي دي اللي هتكسبه.
بس خد بالك إن أنت إيه، اللي قدامك برضه بيلعب optimal يعني. هو الخيار اللي قدامي ممكن ما آخدش الـ maximum دلوقتي بس هو ده اللي هيكسبني بعدين يعني. آه. آه تمام. تمام؟ زياد برضه إن ممكن اللعبة دي نغير فيها شوية بحيث إن أنت أصلًا ما تعرفش، ما تعرفش، يعني ممكن نقول بقى إن العملات.
بتبقى مستخبية، وأنت بس بتكشف على العملتين اللي عليهم الدور، فاهمين؟ يعني العملات أنت مش عارف قيمهم من الأول. فاهمين الفكرة؟ فهي لو كده يبقى أنت أصلًا، يبقى أنت مستحيل تبقى عارف يعني، الـ greedy choice بتاعك يعني. مفهوم الفكرة؟ تمام. أيوة أيوة.
أه تمام. يبقى احنا عندنا DP. طيب، أنهي واحدة من الثلاثة؟ Substring. ممتاز. ليه بقى؟ لإن أنت، هي اللعبة أصلًا كده، اللعبة أنت يعني بتاخد يا العملة الأولى يا العملة الأخيرة، واللي قدامك برضه نفس الفكرة. فاللي بيبقى متفضـ، اللي بيبقى متبقي عندك بيقل من الناحيتين، يا يقل من الناحية دي يا يقل من الناحية دي.
أه صح. فدايمًا الـ subproblems هتقل من الناحيتين، دي أو دي، على حسب أنت اخترت مين واللي قدامك اختار إيه. يبقى هي إيه؟ Substring. ممتاز. تعالوا بقى نعملها مع بعض كده سريعًا، define a problem. ها، coin game. Coin game، عايز أرجع الـ maximum.
total values. إيه الـ parameters؟ الـ coins اللي باقية. هي طبعًا الـ coins okay، أكيد parameter. بس ما تنساش احنا بنتكلم على الـ parameters اللي بتشكل حجم المسألة.
start عند index. بالظبط، احنا اتفقنا إن هي substring. مين الـ start ومين الـ end؟ أو مين الـ left ومين الـ right؟ صح؟ فأنت في الـ main، أما تيجي تنادي عليها في الـ main، هتقول أنا عايز أحسن حل assuming إن أنا هلعب الأول. ما دام هلعب الأول يبقى أنا قدامي الـ coins من واحد إلى n.
n. صح؟ ده الـ main بتاعي، وده الـ result. ده الـ problem. وأكيد طبعًا الـ coins والحاجات دي معانا، بس يعني مش دي الـ parameters المهمة يعني. إيه الـ possibilities بقى اللي عندنا؟ الـ divide and conquer solution، الخطوة الأهم، ودي يمكن اللي احنا هنكتفي بيها يعني، هنقف عندها وأسيب لكم الباقي تكملوه، ها؟ إن شاء الله يعني. إيه الـ possibilities اللي عندنا؟
ده الـ player الأولاني. يا يختار من اليمين فينادي 1 لـ n-1. أيوة. يا من الشمال فـ يـ recurse على إيه؟ 2 لـ n. ممتاز. يبقى أنا قدامي هنا يا، يا هيـ select الشمال.
يا هيـ select اليمين، صح؟ يا هيـ select الشمال يا هيـ select اليمين. لو هو اختار الشمال، اختار الـ coin اللي على الشمال. المرة الجاية، المرة اللي جاية player 1، خلي بالك أنت كل ده بتـ optimize لمين؟
أنت بتـ optimize for the first player. خلاص؟ فالمرة الجاية player 1 هيبقى قدامه مين؟ إيه الاختيارات اللي قدامه لو هو اختار العملة اللي على الشمال؟ يا إما الشمال.
plus 2، أو الشمال plus 1 واليمين minus 1. ممتاز، ليه بقى؟ عشان هو هيكون اختار الشمال فاللي قدامه يا إما هيختار اليمين يا إما الشمال minus 1. اللي هو player رقم two، يا إما هيختار دي يا إما هيختار دي.
ده player 2. وبالتالي player 1 المرة الجاية، المرة الجاية لـ player 1 هيبقى قدامه إيه؟ يا إما coin game left plus 2 لحد الـ right، ده في حالة إن هو إن player 2 اختار دي. يبقى أنا قدامي المرة الجاية هبتدي من هنا.
أو coin game left plus 1 وright minus 1. ده في حالة إن player 2 اختار دي. يبقى أنا قدامي المرة الجاية هبتدي من هنا. صح؟ وسواء دي أو دي، أنت اخترت العملة اللي على الشمال، صح؟
صح؟ يعني قيمتها هتبقى معاك، الـ value بتاعة الـ left هتبقى معاك. ما تنساش تجمعها معاك، خلاص؟ طيب ده بالنسبة للشمال. من الاثنين دول أنت تشتغل على أنهي واحدة فيهم؟
كـ player 1 تشتغل على أنهي واحدة من الاثنين دول؟ الـ maximum ولا الـ minimum؟ يعني إيه؟ طب خلينا دلوقتي طيب، خلينا نرجع لدي كمان شوية، طب لو احنا اخترنا اليمين، السيناريو الثاني.
لو player 1 اختار اليمين، ما اختارش الشمال، اختار اليمين، ده player 1. المرة الجاية إيه الـ options اللي قدامه؟ من left لـ right minus 2 أو من left plus 1 لغاية minus 1. بالظبط، من left لـ right minus 2 أو.
من left plus 1 إلى right minus 1. وسواء دي أو دي، كده كده هجمع عليهم الـ value بتاعة الـ right. جميل. طيب، أنت بقى عايز من دول، من option 1 و option 2 عايز مين؟ أنت هتجرب دي وهتجرب دي، عايز مين منهم؟
maximum ولا minimum؟ ما هو ده هيرجع حل وده هيرجع حل. عايز maximum. صح ممتاز، عايز maximum. أنت كـ player 1 عايز maximum. طيب، بس أنت جوه كل option منهم في two options، صح؟ تشتغل على مين من دول؟ الـ maximum ولا الـ minimum؟
ما أنت قدامك يعني، هل هل تجيب الـ maximum من الأربعة كلهم؟ يعني كإنك بتجيب max max، max لدول وmax لدول وبعدين max الـ total؟ ولا تجيب للي جوه minimum؟ لأ max الكل. ده المنطقي، بس ما تنساش إن في معلومة قلناها إن اللي قدامك بيلعب إيه؟
optimal اللى هو يكون نجبله اوحش حاجة. بالظبط، يعني أنت بتفترض اللي قدامك كمان بيلعب بنصاحة زيك، مش فاشل يعني. فاللي قدامك بيلعب optimal، يبقى هيسيب لك مين؟ يعني ما هو الـ two options دول جايين من فين؟ جايين إن اللي قدامك لعب. دول مش بمزاجك، دول بمزاج اللي قدامك، يعني اللي قدامك هو اللي هيلعب فهيسيب لك واحدة من الاثنين دول.
يبقى أنت الاثنين دول مش بمزاجك، الاثنين دول أنت مجبر هتلعب على واحدة منهم. فلو اللي قدامك بيلعب optimal، هيجبرك إن أنت تلعب على مين من دول؟ الـ minimum فيهم. الـ minimum فيهم، ممتاز. عشان كده بيسموها max min أو mini max. بتـ minimize وبعدين تـ maximize. يبقى أنت من دول تجيب minimum ومن دول تجيب minimum وبعدين تجيب maximum، assuming إن اللي قدامك بيلعب
طيب، كده احنا عملنا الـ possibilities وعملنا الـ subproblems. إيه الـ base case؟ إن الـ right يساوي الـ left. أه، إن الـ left left، يعني ما فيش items، يبقى أنت هترجع مين؟ هتـ return الـ value بتاعة الـ left. أو في ممكن base case ثانية، coin game، لو فاضل لك مين...
لو فاضل لك اثنين، يعني left وleft plus 1، هترجع مين؟ والدور عليك طبعًا. هترجع مين؟ الـ max. الـ max. بس، ده base case، يعني دول two base cases ممكن تقف عندهم. فاضل بقى إن أنت تـ relate الكلام ده، طبعًا الـ relation بتاعه هو coin game.
left وright، وفي الآخر بيرجع الـ value. والله لو الـ left ساوى الـ right، رجع value بتاعة واحدة منهم. else، لو الـ left، الـ right ساوى left plus 1، يعني كان الفرق ما بينهم واحد، رجع الـ maximum.
ما بين الـ left والـ right. else، هتجرب الأربعة options دول، هتجيب الأول option 1 اللي هو عبارة عن الـ minimum ما بين حاجتين اللي هم دول.
وoption 2، هتجيب الـ minimum ما بين قيمتين اللي هم دول. دول الـ left وده الـ option 1. ده option 2. وبعدين هتـ return الـ maximum من option 1 و
option 2. في overlap؟ واضحة من الأول أصلًا، من أول subproblem أهي، left plus 1 و r minus 1، left plus 1 و r minus 1، يعني من الأول خالص فيها overlap. الـ switching، systematic way، هسيبه لكم تعملوه.
top down ولا bottom up؟ إيه الأنفع هنا؟ top down. هل بتجرب كله ولا في subproblems بيحصلها skipping؟ بنعمل skipping. top down هيبقى أحسن. ليه؟ لأ بنجرب كله. أنت لو خليت بالك أنت بتجرب كل أو معظم، لإن أنت عمال تزود واحد من هنا وتنقص واحد من هنا.
أو تزود واحد هنا وتسيب الثاني زي ما هو، صح؟ تزود اثنين هنا وتسيب الثاني زي ما هو، يعني في problems بيحصلها skipping بس مش، مش العدد الأكبر يعني. فأنت في الغالب النسبة هنا هتميل لصالح الـ bottom up بسبب إن معظم الـ subproblems بتحتاج ت
نحسبها عندك +1 هنا، -1 هنا، وبعدين +2 هنا والثاني بيثبت، أو -2 هنا والثاني بيثبت. فأنت في الغالب بتـ skip واحدة بين كل واحدة، يعني كل مرة بتـ skip واحدة بس يعني، اللي هي -1 والـ left أو left + 1 والـ right. يعني...
أتمنى يعني دي بقى هسيب لكم الـ switching تعملوه bottom up وممكن تجربه برضه top down وكذلك الـ construct solution. دي برضه بعض التفاصيل. فكرة سريعة كده عن الـ switching للـ bottom up بتاع مسألة الـ alternating coin game. لو دي الـ matrix أهي هي n في n من 0 لحد n-1، ده الـ left وده الـ right، أو ممكن نخليها من 1 لـ n، مش فارقة. طبعًا خطوات الـ switching الأول بنـ define الـ storage وبعدين الـ equation اللي بنملى بيها، فطبعًا الـ equation اللي هنملى بيها هي...
هي اللي جبناها من الحل اللي كان في الـ slide اللي فات. قيمة الـ value عند الـ left والـ right، الـ base case بتاعها لو الـ left بيساوي الـ right هناخد الـ left، أو لو الـ right بيساوي left + 1 يعني فاضل two items فبناخد الـ maximum ما بينهم. وهم دول الـ marked هنا بالـ green على اللي هو يعتبر الـ diagonal واللي بعده في الـ matrix. فدول الـ base case اللي احنا already عارفينهم.
Next، طبعًا غير كده بنملى بالـ minimum بقى اللي هي بالـ equation اللي شفناها في الـ slide اللي فات. طيب، السؤال اللي بعده بقى، نبتدي من فين؟ يعني أما نيجي نـ fill الـ matrix دي عشان نقدر نملاها بـ loops، نبتدي من فين؟ طبعًا المفروض الصح إن احنا نبتدي من الـ base case. فعشان نعرف نبتدي من فين بالظبط، ده الـ base case.
اللي هو ده اللي احنا أوريدي عارفينه اللي هو 0 0، 1 1، 2 و2، وكذلك اللي بعده. فدول اللي احنا هنبتدي منهم أكيد. طيب نمشي الـ loop إزاي بقى؟ ده السؤال المهم، بنحتاج نعرفه في بعض المسائل خاصة اللي بيبقى فيها أكتر من loop يعني أو أكتر من dimension. عشان نعرف الـ correct loop order محتاجين نشوف احنا given أي subproblem عندنا عند l وr.
left وright، generally بنحتاج عشان نحسبها بنحتاج مين؟ مين الـ subproblems اللي بنحتاجها؟ فلو بصينا تحت هنا هنلاقي إن احنا بنحتاج left + 1 وright - 1، وleft + 2 وright، وleft وright - 2. دول الـ three subproblems اللي بتحتاجهم فلازم نضمن يبقى اتجاه الحل اللي هنحل بيه أو الـ loop order اللي هنحل بيه لازم يضمن لنا إن الثلاثة دول عند أي cell، الثلاثة دول لازم...
يكونوا محسوبين مسبقًا، وبالتالي يبقى كده الـ correct loop order لو احنا هنبتدي من الـ circles من الـ base case اللي هو i وi لكل i من 0 لحد n-1 اللي هم الـ circles اللي بالـ orange دي، فالاتجاه الحل المفروض نمشي بيه هو لفوق، الأسهم كده زي ما واضح في الأسهم هنا. ليه لفوق؟ علشان نضمن إن احنا دايمًا عند أي cell هنحسبها.
عند أي cell هنحتاج نحسبها نلاقي الثلاثة اللي احنا عايزينهم موجودين. اللي تحتينا اللي هي دي موجودة والـ left وright - 2 موجودة وleft + 2 وright برضه موجودة عند أي cell بقى، كذلك أما نيجي نحسب دي هنلاقي إن اللي تحتنا موجودة ودي موجودة ودي موجودة وهكذا. فاتجاه الحل لازم يمشي بالترتيب ده ثاني.
نبتدي من الشمال لليمين ومن تحت لفوق. طبعًا الجزء ده من الـ matrix اللي هو الـ upper half، الـ lower half آسف، بتاعة الـ matrix اللي تحت الـ diagonal، ده مش محتاجين نحسبه أصلًا، ده أصلًا عمره ما هيحصل، لإن الجزء ده معناها إن الـ left عدى الـ right، احنا عمر ما الـ left هيعدي الـ right. عشان كده بنحل نص الـ matrix وبالتالي تقريبًا roughly.
نسبة الـ subproblems اللي هتتحل حوالي 50%، ده برضه بيخلي الـ bottom up في الغالب يبقى أسرع من الـ top down حتى مع رغم إن هي 50% تقريبًا من المسائل بتتحل. بعد كده الـ final solution اللي بندور عليه هو عند 0 وn-1 اللي هي الـ cell دي. ده كده كانت فكرة سريعة عن الـ code، طبعًا أما نملا الـ matrix دي أو النص ده من الـ matrix.
هناخد complexity n square. هسيب لكم بقى إزاي تكتبوا الـ code بتاعها كـ task لحضراتكم. شكرًا جزيلًا، وبالتوفيق إن شاء الله. كده احنا خلصنا المحاضرة، أنا بعتذر طبعًا على الإطالة معلش، هختم بس في حوالي دقيقتين أو ثلاثة conclusion كده سريعًا. شفنا إن الـ dynamic فعلًا useful لإن بيحل problems كتير وبيفرق في الـ complexity بتاعتها بيحولها من...
بفكرة إعادة الاستخدام دي بيحولها من exponential إلى polynomial. وشفناها ده في مسائل كتير، شفناها تقريبًا في الست مسائل اللي خدناها أو الخمسة. الـ Fibonacci اتحولت من 2 power n إلى n، الـ rod cutting من 2 power n إلى n square، الـ knapsack اللي شفناها النهارده من 2 power n لـ wn. وكلهم من 2 power n إلى n square أو wn يعني. فواضح من exponential إلى polynomial.
فمن حاجة ما ينفعش تتنفذ إلى حاجة ينفع تتنفذ فعلًا. الحقيقة المسائل اللي احنا اخترناها دي كانت بتخدم features في مسائل الـ dynamic كلها. إنما نيجي نـ summarize مسائل الـ dynamic، هتلاقي إن في كده varieties من مسائل الـ dynamic، حاولنا نجمع الـ options دي في الجدول ده. أولًا من ناحية الـ subproblems.
الـ subproblems كان فيه suffixes، prefixes، substrings، وساعات بيبقى في مسائل بتشتغل على multiple sequences، مش مش single sequence. بس دي لسه يمكن ما خدناهاش في المحاضرة، هتاخدوها في السكشن إن شاء الله. تلاحظ بقى إن احنا المسائل اللي خدناها بتحاول تـ cover يعني الأربعة، يعني suffixes خدنا حاجات تـ cover، الـ prefixes خدنا برضه حاجات تـ cover، الـ substrings، الـ coin game كانت بتـ cover.
الـ multiple sequences دي هتاخدوها في اللاب إن شاء الله، بتشتغل على أكتر من sequence اللي هي الـ edit distance مثلًا أو موجودة في المحاضرة هنا للي عايز interested إن هو يبص عليها. في برضه subproblems بتبقى integer، يعني الـ problem مش مش شغالة على sequence، هي شغالة على integer وعمال بيقل أو بيزيد، زي مثلًا الـ Fibonacci. الـ Fibonacci ما كانتش sequence، ما فيش أرقام، يعني ما فيش sequence.
وأنا عمال، أو substrings أو subsequences. لأ هي أرقام وعمالة بتقل. زي الـ knapsack، الـ W الـ weight بتاع الـ knapsack كان بيقل إزاي؟ بيقل كـ integer، خلاص؟ وكذلك في برضه subproblems بتبقى عبارة عن vertices، ده هتبان مع الـ graph إن شاء الله قدام، هنرجع ثاني لمثال لو في وقت إن شاء الله في المتبقي في الكورس يعني، هنرجع لمسألة على الـ dynamic على الـ
طيب الـ option الثاني من ناحية الـ constraints اللي بتبقى على الـ subproblems أو الـ expansion. يعني هل في constraint على الـ subproblem أو الـ expansion ولا لأ، إن هي تـ expand أو تـ limit ولا لأ؟ هنا يمكن الـ coin game كان فيها constraint إن أنت كان عندك two subproblems ولازم تختار الـ minimum كل مرة. يعني أنت مجبر إن أنت تشتغل على فين واللي قدامك بيسيب لك اثنين تختار منهم الـ minimum، فدي constraint.
قدام برضه هناخد الـ expansion بتاع الـ subproblems بتاع الـ Bellman-Ford. يعني هنا الـ coin change كانت بتـ expand كل مرة على اثنين، كل مرة بيبقى في two subproblems تختار منهم. في بقى بتـ expand n، factor في n، ده زي الـ Bellman-Ford اللي هو قدام إن شاء الله هناخده. الـ relation اللي ما بين الـ subproblems وبعضها
كل subproblem بتنزل على كام subproblem تحتها؟ في اللي بينزل بـ order 1 branching يعني 2, 3 يعني دايمًا الرقم ثابت. زي معظم اللي خدناها، الـ knapsack، الـ coin game، الـ knapsack بتنزل مسألتين كل مرة، الـ coin change، الـ coin game بتنزل اثنين أو يعني أربعة وتختار منهم. في مسائل ثانية هتاخدوها في السكشن. فبرضه order 1 branching، في order بالـ degree بعدد الـ.
الـ vertices، ده هناخده في الـ Bellman-Ford. فتلاحظ يعني دي تم اختيارها عشان تـ cover بعض الـ features اللي ما حصلهاش covering في مسائل قبل كده، وهكذا يعني هتلاقوا إن احنا بنحاول نـ cover كله. في order n branching زي الـ rod cutting، لو تفتكروا كنا بنجرب n options كل مرة، أو الـ text justification كنا بنجرب n options كل مرة. وفي إن أنت...
بتـ combine multiple solutions من غير فكرة الـ branching أصلًا، يعني ما هياش path في graph في directed acyclic graph، لأ. ده أنت بتـ combine solutions فقط زي الـ Fibonacci. يعني كل دول بيدوروا على minimum أو maximum، بس الـ Fibonacci مش بيدور على minimum ولا maximum، هو عايز الاثنين مع بعض، هو بيجمعهم.
فهو بيـ combine. الأقصد إن هي دي تقريبًا معظم الـ options اللي بتلاقوها في مسائل الـ dynamic، فاحنا حاولنا نعمل لها covering من خلال بقى مسائل المحاضرات أو السكاشن إن شاء الله. Finally، الـ original problem ممكن في منها اللي بيـ combine multiple subproblems. يعني وأنت في الـ original problem مش بتنادي على مسألة واحدة، يعني في الـ main مش بتنادي على واحدة، احنا كل اللي خدناهم بالمناسبة في المحاضرات.
حتى الآن بننادي على واحدة بس في الـ main. السكشن الأسبوع ده هتاخدوا إن أنت في الـ main هتنادي على مسألتين، وقدام إن شاء الله هناخد إن احنا في الـ main هننادي على n مسألة وتختار منهم الـ minimum أو الـ maximum يعني. ده كان summary، ده sheet questions. أتمنى تكون المحاضرة فاتت حضراتكم، بشكركم على الاهتمام وعلى الحضور وبعتذر جدًا على الإطالة.
أشكركم شكرًا جزيلًا يا شباب ونشوفكم على خير إن شاء الله الأسبوع اللي جاي. السلام عليكم ورحمة الله وبركاته.