المكتبة العربية لعلوم الحاسوب
مرحباً بالخوارزميات › البرمجة الديناميكية 16 / 19 السابق التالي

تمارين

مراجعة المفاهيم

متى تكون البرمجة الديناميكية مناسبة؟

يقول أحد الطلاب: «كلما أمكن كتابة علاقة تعاودية، وجب استخدام البرمجة الديناميكية.» لكل مهمة مما يلي، حدّد هل البرمجة الديناميكية أم التتبّع الرجعي أم حلقة أو صيغة رياضية دون جدول dp هي الأنسب. واذكر سبباً رئيسياً واحداً.

  1. باستخدام فئات العملات [1, 3, 4]، كوّن مبلغاً قدره 6 بأقل عدد من العملات. ويجوز استخدام كل فئة مراراً.

  2. أخرِج جميع تباديل [1, 2, 3].

  3. احسب 1+2+⋯+n1 + 2 + \dots + n.

    وبالنسبة إلى المهمة التي تراها مناسبة للبرمجة الديناميكية، اذكر أيضاً ما يمثّله dp[i].

الإجابة

  1. البرمجة الديناميكية مناسبة. ليكُن dp[i] أدنى عدد من العملات اللازمة لتكوين المبلغ i. فلكل عملة c لا تتجاوز i، يكون dp[i-c] + 1 إجابة مرشحة، ويُختار الحد الأدنى من هذه المرشحات. فالاختيارات المختلفة تصادف المبالغ نفسها مراراً، ويمكن بناء حل أمثل لمبلغ أكبر من حلول مثلى لمبالغ أصغر. وإجابة المبلغ 6 هي 2، باستخدام 3 + 3.

  2. التتبّع الرجعي مناسب. تتطلب المهمة توليد التباديل الستة جميعها واحداً واحداً. ويستطيع التتبّع الرجعي اتخاذ اختيار بشكل منهجي، ومواصلة البحث، والتراجع عن الاختيار، ثم تجربة فرع آخر. وأياً كانت الطريقة، فإن إخراج كل تبديل فعلياً يقتضي تعديده.

  3. تكفي حلقة أو صيغة المتتالية الحسابية. فرغم إمكان كتابة العلاقة التعاودية S(i) = S(i-1) + i، فإن حساب S(i) يعتمد على قيمة أصغر واحدة فقط هي S(i-1). ولا يلزم حساب كل مجموع جزئي إلا مرة واحدة، فلا توجد مسائل فرعية مكررة ولا حاجة إلى جدول dp. و«إمكان كتابة علاقة تعاودية» لا يعني «الحاجة إلى البرمجة الديناميكية».

حساب خلية واحدة في جدول الحقيبة

لننظر في مسألة حقيبة 0-1 التالية: أوزان العناصر wgt = [1, 2, 3]، وقيمها val = [5, 11, 15]، وسعة الحقيبة 4. وdp[i][c] هي أقصى قيمة يمكن الحصول عليها باستخدام أول ii من العناصر بحد سعة حقيبة cc؛ ولا يلزم ملء الحقيبة بدقة.

احسب الحالة dp[3][4] فقط. والمعطى dp[2][4] = 16 وdp[2][1] = 5:

  1. إذا لم يُختَر العنصر الثالث، فما القيمة المرشحة؟
  2. إذا اختير العنصر الثالث، فكم تبقى من سعة، وما القيمة المرشحة؟
  3. كم ينبغي أن تكون dp[3][4]؟ وأي العناصر يقابل اختيارها هذه القيمة؟

الإجابة

  1. إذا لم يُختَر العنصر الثالث، فاحتفظ بالنتيجة الناتجة من العنصرين الأولين. والقيمة المرشحة هي dp[2][4] = 16.

  2. وزن العنصر الثالث 3، لذا تبقى سعة 4−3=14-3=1 بعد وضعه في الحقيبة. والقيمة المرشحة هي dp[2][1] + 15 = 5 + 15 = 20.

  3. بمقارنة 16 و20 نحصل على dp[3][4] = 20. وهذا يقابل اختيار العنصرين الأول والثالث، اللذين يساوي وزنهما الإجمالي 1+3=41+3=4 وقيمتهما الإجمالية 5+15=205+15=20.

    ويوضح حساب هذه الحالة مقارنة واحدة من نوع «الاختيار أو عدم الاختيار» في مسألة حقيبة 0-1.

بأي ترتيب ينبغي تحديث سعات الحقيبة؟

تحتوي مسألة حقيبة 0-1 على عنصر واحد فقط، وزنه 2 وقيمته 5، وسعة الحقيبة 4. ويمكن اختيار العنصر مرة واحدة على الأكثر. والمصفوفة الأحادية البعد الأولية هي dp = [0, 0, 0, 0, 0].

يعالج أحد الطلاب العنصر بتحديث السعات من 2 إلى 4:

  • بعد تحديث dp[2]، تصبح قيمته 5.
  • بعد تحديث dp[3]، تصبح قيمته 5 أيضاً.
  • عند تحديث dp[4]، يستخدم الطالب قيمة dp[2] التي حصل عليها حديثاً، فينتج dp[4] = 10.
  1. هل dp[4] = 10 صحيحة؟ ولماذا أو لماذا لا؟
  2. بما أن كل عنصر يمكن اختياره مرة واحدة على الأكثر، فماذا ينبغي أن تكون dp[4]؟
  3. عند معالجة كل عنصر، هل ينبغي تحديث السعات من الأكبر إلى الأصغر أم من الأصغر إلى الأكبر؟ وما المشكلة التي يتجنبها ذلك؟

الإجابة

  1. النتيجة غير صحيحة. فقيمة 10 تكافئ وضع العنصر ذي القيمة 5 في الحقيبة مرتين، مما يخالف شرط اختيار كل عنصر مرة واحدة على الأكثر.

  2. يمكن للحقيبة أن تحتوي هذا العنصر الواحد على الأكثر، لذا فإن القيمة الصحيحة لـdp[4] هي 5.

  3. ينبغي تحديث السعات من الأكبر إلى الأصغر، بالترتيب 4 ثم 3 ثم 2. وبذلك، عند حساب dp[c]، تظل القيمة المقروءة من dp[c-2] ناتجة مما قبل معالجة العنصر الحالي، مما يمنع إعادة استخدام العنصر الحالي في الجولة نفسها.

تمارين برمجية

عدد طرق صعود الدرج

يتكوّن الدرج من n درجة. وكل حركة تصعد درجة واحدة أو درجتين، ويجب أن تنتهي بالضبط عند الدرجة n. احسب عدد الطرق المتمايزة للوصول إلى القمة. افترض أن n >= 1؛ ولا تتمايز الطرق إلا بمتتالية حركات الدرجة الواحدة والدرجتين. استخدم مصفوفة برمجة ديناميكية أحادية البعد. ولا تستخدم الآن تحسين المساحة الذي يحتفظ بحالتين فقط.

تلميحات

  1. يمكن للحركة الأخيرة إلى الدرجة i أن تغطي درجة واحدة أو درجتين فقط
  2. لذلك dp[i] = dp[i-1] + dp[i-2]
  3. عالج أولاً الحالتين n = 1 و n = 2، ثم املأ الجدول ابتداءً من الدرجة 3

LeetCode{ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }

حقيبة 0-1

معطى مصفوفتان متساويتا الطول wgt وval. وللعنصر i وزن صحيح موجب wgt[i] وقيمة صحيحة غير سالبة val[i]. وسعة الحقيبة cap عدد صحيح غير سالب. ويمكن اختيار كل عنصر مرة واحدة على الأكثر. ابحث عن أقصى قيمة إجمالية يمكن وضعها في الحقيبة دون تجاوز cap. استخدم البرمجة الديناميكية أحادية البعد.

تلميحات

  1. هيّئ مصفوفة dp طولها cap + 1، حيث dp[c] هي أقصى قيمة في حدود سعة c
  2. عند معالجة العنصر i، قارن dp[c] الذي لا يختاره بـ dp[c-wgt[i]] + val[i] الذي يختاره
  3. حدّث السعات من الأكبر إلى الأصغر لتجنّب اختيار العنصر الحالي مراراً في الجولة نفسها
السابق ملخص التالي الجشع