تمارين
مراجعة المفاهيم
هل اختيار أكبر عملة هو الأفضل دائماً؟
فئات العملات هي [1, 7, 10]، والمبلغ الهدف 14.
- اتبع القاعدة «اختر دائماً أكبر فئة لا تتجاوز المبلغ المتبقي»، واكتب العملات المختارة.
- هل يوجد حل يستخدم عملات أقل؟ إن وُجد فأعطِ مثالاً، وإلا فاشرح السبب.
- هل يبيّن هذا المثال أن الاستراتيجية الجشعة صحيحة لكل مجموعة من فئات العملات؟
الإجابة
-
تختار الاستراتيجية الجشعة
10 + 1 + 1 + 1 + 1، باستخدام 5 عملات إجمالاً. -
يوجد حل يستخدم عملات أقل:
7 + 7، وهو يستخدم عملتين فقط. -
لا. يبيّن هذا المثال المضاد أن اختيار أكبر فئة متاحة حالياً مراراً لا يضمن بالضرورة تقليل عدد العملات مع فئات عملات عشوائية. فالاختيار الأكبر الفوري قد يمنع توليفة أفضل لاحقاً.
أي عنصر يجب وضعه في الحقيبة أولاً؟
يمكن لحقيبة سعتها 4 كيلوغرامات أن تحمل العنصرين الآتيين. ويجوز أخذ جزء من العنصر، وتكون القيمة المتحصلة متناسبة مع وزنه:
- العنصر A: وزنه 4 كيلوغرامات، وقيمته 20.
- العنصر B: وزنه 3 كيلوغرامات، وقيمته 18.
- ما قيمة كل عنصر لكل كيلوغرام؟ وأي عنصر يجب وضعه في الحقيبة أولاً؟
- املأ الحقيبة باستخدام الاستراتيجية الجشعة لمسألة الحقيبة الكسرية. فما القيمة النهائية؟
- عندما يمكن تجزئة العناصر وتحدّ الحقيبة من الوزن الإجمالي، فهل تُقارَن العناصر بالقيمة الإجمالية أم بالقيمة لكل كيلوغرام؟ ولماذا؟
الإجابة
-
قيمة A هي
20 ÷ 4 = 5لكل كيلوغرام، بينما قيمة B هي18 ÷ 3 = 6لكل كيلوغرام، لذا يجب وضع B، ذي القيمة الأعلى لكل وحدة وزن، في الحقيبة أولاً. -
خُذ B كاملاً أولاً، مستهلكاً 3 كيلوغرامات من السعة وكاسباً قيمة 18. وبتبقّي كيلوغرام واحد من السعة، خُذ كيلوغراماً واحداً من A، كاسباً قيمة 5. فتكون القيمة النهائية
18 + 5 = 23. -
تحدّ الحقيبة من الوزن الإجمالي، ويمكن تجزئة العناصر، لذا يجب مقارنتها بالقيمة لكل وحدة وزن. فرغم أن قيمة A الإجمالية أعلى، فإن قيمتها لكل كيلوغرام أقل من قيمة B. وملء الحقيبة بـ A أولاً لن يعطي سوى قيمة 20.
أي مؤشر يجب تحريكه تالياً؟
ارتفاعات الحواجز هي [1, 8, 6, 2, 5]. استخدم مؤشرين، أحدهما عند كل طرف، لإيجاد أقصى سعة.
والسعة تساوي «ارتفاع الحاجز الأقصر × المسافة بين فهرسي الحاجزين».
- في البداية، يقع المؤشر الأيسر عند الفهرس 0 والمؤشر الأيمن عند الفهرس 4. فما السعة الحالية؟ وأي مؤشر يجب تحريكه تالياً؟
- بعد تنفيذ الحركة المختارة في السؤال 1، عند أي فهرس يقع المؤشران؟ وما السعة الآن؟ وأي مؤشر يجب تحريكه تالياً؟
- بالنسبة إلى زوج الحواجز الحالي، يمكنك تحريك المؤشر عند الحاجز الأقصر أو المؤشر عند الحاجز الأطول. فأي الحركتين قد تنتج سعة أكبر، ولماذا؟
الإجابة
-
السعة الحالية
min(1, 5) × (4 - 0) = 4. الحاجز الأيسر أقصر، لذا حرّك المؤشر الأيسر. -
بعد تحرك المؤشر الأيسر، يقع المؤشران عند الفهرسين 1 و4. والسعة الحالية
min(8, 5) × (4 - 1) = 15. الحاجز الأيمن أقصر، لذا حرّك المؤشر الأيمن تالياً. -
تحريك المؤشر عند الحاجز الأقصر هو الحركة الوحيدة التي قد تنتج سعة أكبر. فإذا تحرك مؤشر الحاجز الأطول، تنقص المسافة قطعاً بينما يظل الارتفاع محدوداً بالحاجز الأقصر غير المتحرك، لذا لا يمكن للسعة إلا أن تبقى كما هي أو تنقص. ولا يمكن العثور على حاجز أطول إلا بتحريك الحاجز الأقصر.
تمارين برمجية
الحقيبة الكسرية
معطى مصفوفتان متساويتا الطول wgt وval، حيث wgt[i] > 0 وval[i] >= 0. وسعة الحقيبة cap >= 0.
ويوجد من كل عنصر نسخة واحدة فقط، لكن يجوز وضع أي جزء من العنصر في الحقيبة.
وتتناسب القيمة المتحصلة مع نسبة ما يُضمَّن من الوزن الإجمالي للعنصر. استخدم خوارزمية جشعة
وأعد أقصى قيمة إجمالية يمكن أن تحملها الحقيبة على هيئة عدد حقيقي.
تلميحات
- احسب أولاً قيمة كل عنصر لكل وحدة وزن بالصيغة val[i] / wgt[i]، مع الاحتفاظ بالجزء الكسري من القسمة
- ضع العناصر ذات القيمة الأعلى لكل وحدة وزن في الحقيبة أولاً
- إذا كانت السعة المتبقية أقل من وزن العنصر الحالي، فخُذ بالضبط الكسر الذي يملأ الحقيبة ثم توقف