الدرس 2 من 7
تلخيص درس خوارزميات تعبئة الصناديق
الدرس باختصار
مسألة تعبئة الصندوق تسأل: كيف نضع عناصر مختلفة المقاسات في أقل عدد ممكن من الصناديق ذات السعة الواحدة؟ نستعملها في تحميل البضائع في الشاحنات، وترتيب الأغراض على الرفوف، وتخزين الملفات على الأقراص، وقصّ القماش من لفّات كبيرة.
مصطلحات الدرس
- خوارزميات تعبئة الصناديق
- طرائق منظّمة بخطوات محدّدة لتوزيع العناصر على الصناديق بأقل عدد ممكن منها.
- الحدّ الأدنى لعدد الصناديق
- أصغر عدد صحيح من الصناديق يمكن أن يتّسع لمجموع مقاسات العناصر؛ نحصل عليه بقسمة المجموع على سعة الصندوق ثم التقريب إلى الأعلى.
- خوارزمية المُلاءَمة الأولى
- نأخذ العناصر بالترتيب المعطى، ونضع كل عنصر في أول صندوق يتّسع له.
- خوارزمية المُلاءَمة الأولى المُتناقِصة
- نرتّب المقاسات من الأكبر إلى الأصغر أولًا، ثم نطبّق المُلاءَمة الأولى.
- خوارزمية الصندوق الكامل
- نبحث أولًا عن عناصر مجموعها يملأ صندوقًا تمامًا ونعبّئها معًا، ثم نطبّق المُلاءَمة الأولى على الباقي.
- الحلّ الأمثل
- حلّ عدد صناديقه يساوي الحدّ الأدنى لعدد الصناديق.
- المهدور
- المساحة الفارغة المتبقية في الصناديق المستعملة.
أهم الأفكار
الحدّ الأدنى لعدد الصناديق
نجمع مقاسات العناصر ونقسم على سعة الصندوق ثم نقرّب إلى الأعلى: . إن ساوى عدد صناديق حلّنا هذا العدد فالحلّ أمثل.
المُلاءَمة الأولى والمُتناقِصة
في الأولى نلتزم الترتيب المعطى، وفي الثانية نرتّب تنازليًا قبل التعبئة. تضع كل منهما العنصر في أول صندوق يتّسع له، وتضيف صندوقًا جديدًا إذا لم يتّسع أي صندوق. الثانية أفضل عادةً لكنها لا تضمن الحلّ الأمثل.
خوارزمية الصندوق الكامل
نملأ أولًا صناديق كاملة من عناصر مجموعها يساوي السعة تمامًا، ثم نعبّئ الباقي بالمُلاءَمة الأولى. تعطي حلًّا جيدًا عادةً لكنها صعبة إذا كثرت العناصر أو كانت أعدادًا عشرية.
حساب المهدور
المهدور = (عدد الصناديق المستعملة × سعة الصندوق) − مجموع المقاسات.
أمثلة محلولة
مثال 1: الحدّ الأدنى لعدد الصناديق
يراد تعبئة عناصر مقاساتها 6, 9, 4, 7, 5, 8, 3, 2, 7 في صناديق سعة كلٍّ منها 12 وحدة. جد الحدّ الأدنى لعدد الصناديق اللازمة.
اعرض الحل
- نجمع المقاسات: .
- نقسم على سعة الصندوق: .
- نقرّب إلى الأعلى لأن الجزء العشري يحتاج صندوقًا إضافيًا كاملًا، فنحصل على 5.
الجواب: الحدّ الأدنى هو صناديق.
مثال 2: المُلاءَمة الأولى والمهدور
عناصر مقاساتها بالترتيب: 5, 7, 4, 6, 3, 8, 2 تُعبّأ في صناديق سعة كلٍّ منها 10. استعمل المُلاءَمة الأولى، وحدّد عدد الصناديق، وهل الحلّ أمثل، ثم جد المهدور الكلي.
اعرض الحل
- المجموع ، و فالحدّ الأدنى 4 صناديق.
- B1: نضع 5 ثم 4 (المجموع 9)، ولا يتّسع الباقي (1 فقط).
- B2: نضع 7 ثم 3 (المجموع 10).
- B3: نضع 6 (المجموع 6) ولا تتّسع 8 فيه، لكن 2 تتّسع لاحقًا (المجموع 8).
- B4: نضع 8 وحدها (ثم 2 تُوضع في B3 كما ذكرنا لأنها أول صندوق يتّسع لها).
- عدد الصناديق 4، يساوي الحدّ الأدنى، فالحلّ أمثل.
- المهدور: .
الجواب: 4 صناديق، الحلّ أمثل، والمهدور وحدات.
مثال 3: المُلاءَمة الأولى المُتناقِصة
عناصر مقاساتها: 2, 7, 4, 5, 3, 6, 1 تُعبّأ في صناديق سعة كلٍّ منها 9. استعمل المُلاءَمة الأولى المُتناقِصة وجد عدد الصناديق والمهدور.
اعرض الحل
- المجموع ، و فالحدّ الأدنى 4 صناديق.
- الترتيب التنازلي: 7, 6, 5, 4, 3, 2, 1.
- B1: 7 ثم 2 (المجموع 9). B2: 6 ثم 3 (المجموع 9).
- B3: 5 ثم 4 (المجموع 9). B4: 1.
- المهدور: وهو كله في الصندوق الأخير.
- عدد الصناديق 4 يساوي الحدّ الأدنى فالحلّ أمثل.
الجواب: 4 صناديق، الحلّ أمثل، والمهدور .
مثال 4: الصندوق الكامل في قصّ القماش
يريد خيّاط قصّ قطع طولها بالمتر: 14, 26, 9, 21, 31, 19, 11, 29 من لفّات طول كلٍّ منها 50 m. جد الحدّ الأدنى لعدد اللفّات، ثم عبّئ بالصندوق الكامل، وجد طول المهدور.
اعرض الحل
- المجموع .
- فالحدّ الأدنى 4 لفّات.
- نبحث عن مجاميع تساوي 50: و.
- بعد ذلك نعبّئ الباقي 14, 26, 9, 11 بالمُلاءَمة الأولى: B3: 14 ثم 26 ثم 9 (المجموع 49)، B4: 11.
- عدد اللفّات 4 يساوي الحدّ الأدنى فالحلّ أمثل.
- المهدور: m.
الجواب: 4 لفّات، والمهدور m.
أخطاء شائعة
تقريب ناتج القسمة إلى أقرب عدد صحيح بدل التقريب إلى الأعلى (مثلًا 4.25 تصبح 4).
ليش غلط: الجزء المتبقي من المقاسات يحتاج صندوقًا إضافيًا، فالتقريب إلى الأسفل يعطي عددًا لا يكفي.
الصح: قرّب دائمًا إلى الأعلى عند إيجاد الحدّ الأدنى لعدد الصناديق.
وضع العنصر في آخر صندوق مفتوح فقط بدل البحث من الصندوق الأول.
ليش غلط: المُلاءَمة الأولى تقتضي فحص الصناديق بدءًا من الأول في كل مرة، وقد يتّسع صندوق سابق لعنصر صغير.
الصح: ابدأ الفحص من B1 لكل عنصر ثم انتقل إلى B2 وهكذا.
الحكم بأن الحلّ أمثل لمجرد استعمال المُلاءَمة الأولى المُتناقِصة.
ليش غلط: هذه الخوارزمية جيدة غالبًا لكنها لا تضمن الأمثل دائمًا.
الصح: قارن عدد الصناديق بالحدّ الأدنى؛ الحلّ أمثل فقط إذا تساويا.
نسيان طرح الأعداد المعبّأة عند حساب المهدور، أو جمع سعات الصناديق بدل المهدور.
ليش غلط: المهدور هو الفراغ المتبقي لا السعة الكلية.
الصح: استعمل: عدد الصناديق × السعة − مجموع المقاسات.
اختبر حالك
1. مجموع مقاسات عناصر 38، وسعة الصندوق 10. ما الحدّ الأدنى لعدد الصناديق؟
اعرض الجواب
الجواب:
ونقرّب إلى الأعلى فنحصل على 4.
2. استُعملت 5 صناديق سعة كلٍّ منها 8، ومجموع المقاسات 33. ما المهدور الكلي؟
اعرض الجواب
الجواب:
.
3. رُتّبت العناصر 3, 8, 5, 2 تنازليًا للمُلاءَمة الأولى المُتناقِصة. اكتب الترتيب الجديد بالصورة (a, b, c, d).
اعرض الجواب
الجواب:
نرتّب من الأكبر إلى الأصغر.
جاهز تتدرّب؟
69 سؤال على هالدرس، بتتصحّح خطوة خطوة، ومعها تلميحات لما تعلق. أول أسئلة مجانية.
تدرّب على 69 سؤال من هالدرس مجانًا