حل اسئلة درس خوارزميات تعبئة الصندوق
٢١ سؤالاً من تمارين الكتاب، مع رقم الصفحة والحل
افتح الموضوع في التطبيق- سؤال من الكتاب · صفحة 64يراد تعبئة العلب (المعطى ارتفاعاتها في ما يلي) في صناديق، ارتفاع كلّ منها 1.5 وحدة طول، علما بأنّ للعلب والصناديق المقطع العرضي نفسه (المثال 2): 0.8 0.6 0.5 0.7 0.9 0.4 0.3 0.6 0.5 0.6 وقد عبّئت باستعمال خوارزمية الملاءمة الأولى في 5 صناديق. أستعمل خوارزمية الملاءمة الأولى المتناقصة لإعادة حلّ المسألة، وأحدّد إذا كان الحلّ الناتج هو الحلّ الأمثل أم لا، وأجد مجموع الارتفاعات المهدورة في الصناديق جميعها، ثمّ أقارن الحلّ الذي توصّلت إليه بالحلّ الناتج باستعمال خوارزمية الملاءمة الأولى.
إظهار الحلّإخفاء الحلّ
1. الارتفاعات مرتبة تنازليا: 0.9 0.8 0.7 0.6 0.6 0.6 0.5 0.5 0.4 0.3
2. \frac{0.9 + 0.8 + 0.7 + 0.6 + 0.6 + 0.6 + 0.5 + 0.5 + 0.4 + 0.3}{1.5} = 3.93 \approx 4 الحد الأدنى من عدد الصناديق اللازمة لتعبئة العلب هو 4 صناديق.
3. B_1: 0.9, 0.6 B_2: 0.8, 0.7 B_3: 0.6, 0.6, 0.3 B_4: 0.5, 0.5, 0.4
4. عدد الصناديق اللازمة لتعبئة العلب باستعمال خوارزمية الملاءمة الأولى المتناقصة هو 4 صناديق.
5. توصلنا إلى الحل الأمثل لأن عدد الصناديق المستعملة في هذا الحل يساوي الحد الأدنى من عدد الصناديق اللازمة.
6. الارتفاع المهدور في الصناديق جميعها هو 0.1 وحدة طول.
7. ألاحظ أن هذا الحل أفضل لأن عدد الصناديق المستعملة يساوي الحد الأدنى من عدد الصناديق اللازمة، والجزء المهدور أقل. - سؤال من الكتاب · صفحة 108يراد تعبئة العلب (المعطى ارتفاعاتها في ما يلي) في صناديق، ارتفاع كلّ منها 5 وحدات طول. إذا علمت أنّ للعلب والصناديق المقطع العرضي نفسه، | 2.6 | 0.8 | 2.1 | 1.2 | 0.9 | 1.7 | 2.3 | 0.3 | 1.8 | 2.7 | |---|---|---|---|---|---|---|---|---|---| أستعمل خوارزمية الملاءمة الأولى المتناقصة لتعبئة العلب في الصناديق، ثمّ أحدّد عدد الصناديق اللازمة لذلك، ثمّ أجد مقدار الارتفاع المهدور من الصناديق جميعها.
إظهار الحلّإخفاء الحلّ
B_1: 2.7, 2.3, B_2: 2.6, 2.1, 0.3, B_3: 1.8, 1.7, 1.2, B_4: 0.9, 0.8 عدد الصناديق اللازمة باستعمال خوارزمية الملائمة الأولى المتناقصة هو 4 صناديق. الارتفاع المهدور هو 3.6 = 16.4 - 5 \times 4 - سؤال من الكتاب · صفحة 108يراد تعبئة العلب (المعطى ارتفاعاتها في ما يلي) في صناديق، ارتفاع كلّ منها 5 وحدات طول. إذا علمت أنّ للعلب والصناديق المقطع العرضي نفسه، | 2.6 | 0.8 | 2.1 | 1.2 | 0.9 | 1.7 | 2.3 | 0.3 | 1.8 | 2.7 | |---|---|---|---|---|---|---|---|---|---| أستعمل خوارزمية الملاءمة الأولى لتعبئة العلب في الصناديق، ثمّ أحدّد عدد الصناديق اللازمة لذلك، ثمّ أجد مقدار الارتفاع المهدور من الصناديق جميعها.
إظهار الحلّإخفاء الحلّ
B_1: 2.6, 0.8, 1.2, 0.3, B_2: 2.1, 0.9, 1.7, B_3: 2.3, 1.8, B_4: 2.7 عدد الصناديق اللازمة باستعمال خوارزمية الملائمة الأولى هو 4 صناديق. الارتفاع المهدور هو 3.6 = 16.4 - 5 \times 4 - سؤال من الكتاب · صفحة 108يراد تعبئة العلب (المعطى ارتفاعاتها في ما يلي) في صناديق، ارتفاع كلّ منها 5 وحدات طول. إذا علمت أنّ للعلب والصناديق المقطع العرضي نفسه، | 2.6 | 0.8 | 2.1 | 1.2 | 0.9 | 1.7 | 2.3 | 0.3 | 1.8 | 2.7 | |---|---|---|---|---|---|---|---|---|---| أستعمل خوارزمية الصندوق الكامل لتعبئة العلب في الصناديق، ثمّ أحدّد عدد الصناديق اللازمة لذلك، ثمّ أجد مقدار الارتفاع المهدور من الصناديق جميعها.
إظهار الحلّإخفاء الحلّ
B_1: 2.7, 2.3, B_2: 2.6, 2.1, 0.3, B_3: 0.8, 1.2, 0.9, 1.7, B_4: 1.8 عدد الصناديق اللازمة باستعمال خوارزمية الصندوق الكامل هو 4 صناديق. الارتفاع المهدور هو 3.6 = 16.4 - 5 \times 4 - سؤال من الكتاب · صفحة 69تحدّ: في ما يأتي كتل 9 حقائب سفر (إلى أقرب كيلوغرام) يراد نقلها في حاويات، ويمكن لكلّ منها أن تحمل كتلة إجمالية أقصاها 50 kg: 24 14 8 x 19 25 6 17 9 إذا علمت أنّ كتلة إحدى الحقائب لم تقس قياسا دقيقا، ولتكن x كيلوغراما، حيث: 23 ≥ x > 19، أحدّد القيمة (القيم) الممكنة للمتغير x في كلّ من الطريقتين الممكنتين لتوزيع الحقائب باستعمال خوارزمية الملائمة الأولى المتناقصة.
إظهار الحلّإخفاء الحلّ
قيمة x في الطريقة الأولى هي 23 = x
قيم x في الطريقة الثانية هي 22, 21, 20 - سؤال من الكتاب · صفحة 62يراد تعبئة العلب (المعطى ارتفاعاتها في ما يلي) في صناديق، ارتفاع كلّ منها 20 وحدة طول. إذا علمت أنّ للعلب والصناديق المقطع العرضي نفسه، فأجيب عن الأسئلة التالية تباعا:
11 2 15 5 6 17 7
a) أستعمل خوارزمية الملاءمة الأولى لتعبئة العلب في الصناديق، ثمّ أحدّد عدد الصناديق اللازمة لذلك.
b) هل توصّلت إلى الحل الأمثل لهذه المسألة؟ أبرّر إجابتي.
c) أجد الارتفاع المهدور في الصناديق جميعها.إظهار الحلّإخفاء الحلّ
\frac{11 + 2 + 15 + 5 + 6 + 17 + 7}{20} = 3.15 \approx 4 الحد الأدنى من عدد الصناديق اللازمة لتعبئة العلب هو 4 صناديق.
a. B_1: 11, 2, 5 B_2: 15 B_3: 6, 7 B_4: 17 عدد الصناديق اللازمة لتعبئة العلب باستعمال خوارزمية الملاءمة الأولى هو 4 صناديق.
b. نعم، لأن عدد الصناديق المستعملة في هذا الحل يساوي الحد الأدنى من عدد الصناديق اللازمة.
c. 2 + 5 + 7 + 3 = 17 الارتفاع المهدور في الصناديق جميعها هو 17 وحدة طول. - سؤال من الكتاب · صفحة 69تحدّ: في ما يأتي كتل 9 حقائب سفر (إلى أقرب كيلوغرام) يراد نقلها في حاويات، ويمكن لكلّ منها أن تحمل كتلة إجمالية أقصاها 50 kg: 24 14 8 x 19 25 6 17 9 إذا علمت أنّ كتلة إحدى الحقائب لم تقس قياسا دقيقا، ولتكن x كيلوغراما، حيث: 23 ≥ x > 19، أحدّد الطريقتين الممكنتين لتوزيع الحقائب على الحاويات باستعمال خوارزمية الملائمة الأولى المتناقصة.
إظهار الحلّإخفاء الحلّ
الكتل مرتبة تنازليا: 25, 24, x, 19, 17, 14, 9, 8, 6
الطريقة الأولى: إذا كانت x = 23
B_1: 25, 24
B_2: 23, 19, 8
B_3: 17, 14, 9, 6
عدد الحاويات اللازمة باستعمال خوارزمية الملاءمة الأولى المتناقصة هو 3 حاويات.
الطريقة الثانية: إذا كانت 19 < x < 23
B_1: 25, 24
B_2: x, 19, 9
B_3: 17, 14, 8, 6
عدد الحاويات اللازمة باستعمال خوارزمية الملاءمة الأولى المتناقصة هو 3 حاويات. - سؤال من الكتاب · صفحة 69يراد تعبئة العلب (المعطى ارتفاعاتها في ما يلي) في صناديق، ارتفاع كلّ منها 5 وحدات طول. إذا علمت أنّ للعلب والصناديق المقطع العرضي نفسه، | 1.8 | 1.4 | 2.6 | 1.6 | 2.8 | 0.9 | 3.1 | 0.8 | 1.2 | 2.4 | 0.6 | |---|---|---|---|---|---|---|---|---|---|---| أستعمل خوارزمية الملاءمة الأولى لتعبئة العلب في الصناديق، ثمّ أحدّد عدد الصناديق اللازمة لذلك.
إظهار الحلّإخفاء الحلّ
1. \frac{1.8 + 1.4 + 2.6 + 1.6 + 2.8 + 0.9 + 3.1 + 0.8 + 1.2 + 2.4 + 0.6}{5} = 3.84 \approx 4 الحد الأدنى من عدد الصناديق اللازمة لتعبئة العلب هو 4 صناديق.
2. B_1: 1.8, 1.4, 1.6 B_2: 2.6, 0.9, 0.8, 0.6 B_3: 2.8, 1.2 B_4: 3.1 B_5: 2.4
3. عدد الصناديق اللازمة لتعبئة العلب باستعمال خوارزمية الملاءمة الأولى هو 5 صناديق. - سؤال من الكتاب · صفحة 108شحن: في ما يأتي كتل 10 صناديق (بالكيلوغرام) يراد نقلها في شاحنات، ويمكن لكلّ منها أن تحمل كتلة إجمالية أقصاها 300 kg: | 175 | 135 | 210 | 105 | 100 | 150 | 60 | 20 | 70 | 125 | |---|---|---|---|---|---|---|---|---|---| أحدّد كيف توزّع الصناديق على الشاحنات باستعمال خوارزمية الملاءمة الأولى المتناقصة، ثمّ أحدّد عدد الشاحنات اللازمة لذلك باستعمال هذه الخوارزمية.
إظهار الحلّإخفاء الحلّ
B_1: 210, 70, 20, B_2: 175, 125, B_3: 150, 135, B_4: 105, 100, 60 عدد الشاحنات اللازمة باستعمال خوارزمية الملائمة الأولى المتناقصة هو 4 شاحنات. - سؤال من الكتاب · صفحة 69تبرير: في ما يأتي أطوال 8 قطع خشبية (بالسنتيمتر) تلزم لصنع خزانة صغيرة، ويراد قصّها من ألواح خشبية: 20 35 50 60 20 70 75 20 تتوافر ألواح خشبية، طول كلّ منها 1.5m، وسعرها 4 JD. أستعمل خوارزمية الملائمة الأولى المتناقصة لتحديد كيف تقصّ القطع الخشبية من هذه الألواح، ثمّ أجد التكلفة الكلية لصنع الخزانة باستعمال هذه الخوارزمية، ثمّ أحسب الكمية المهدورة من الخشب.
إظهار الحلّإخفاء الحلّ
B_1: 75, 70 B_2: 60, 50, 35 B_3: 20, 20, 20 عدد الألواح اللازمة باستعمال خوارزمية الملاءمة الأولى المتناقصة هو 3 ألواح. التكلفة الكلية لصنع الخزانة باستعمال خوارزمية الملائمة الأولى المتناقصة هي: 3 \times 4 = 12\ JD الكمية المهدورة من الخشب هي: 3 \times 150 - 350 = 100 \ cm - سؤال من الكتاب · صفحة 69يراد تعبئة العلب (المعطى ارتفاعاتها في ما يلي) في صناديق، ارتفاع كلّ منها 5 وحدات طول. إذا علمت أنّ للعلب والصناديق المقطع العرضي نفسه، فأجيب عن الأسئلة التالية تباعا:
| 1.8 | 1.4 | 2.6 | 1.6 | 2.8 | 0.9 | 3.1 | 0.8 | 1.2 | 2.4 | 0.6 |
|---|---|---|---|---|---|---|---|---|---|---|
استعملت خوارزمية الملاءمة الأولى لتعبئة العلب في الصناديق، فكان الحل:
B1: 1.8, 1.4, 1.6
B2: 2.6, 0.9, 0.8, 0.6
B3: 2.8, 1.2
B4: 3.1
B5: 2.4
أي أنّ عدد الصناديق المستعملة 5 صناديق.
هل هذا الحلّ هو الحلّ الأمثل لهذه المسألة؟ أبرّر إجابتي.إظهار الحلّإخفاء الحلّ
لم نتوصل إلى الحل الأمثل لأن عدد الصناديق المستعملة في هذا الحل لا يساوي الحد الأدنى من عدد الصناديق اللازمة. - سؤال من الكتاب · صفحة 69تبرير: في ما يأتي أطوال 8 قطع خشبية (بالسنتيمتر) تلزم لصنع خزانة صغيرة، ويراد قصّها من ألواح خشبية: 20 35 50 60 20 70 75 20 تتوافر ألواح خشبية، طول كلّ منها 1m، وسعرها 3 JD. أستعمل خوارزمية الملائمة الأولى المتناقصة لتحديد كيف تقصّ القطع الخشبية من الألواح، ثمّ أجد التكلفة الكلية لصنع الخزانة باستعمال هذه الخوارزمية، ثمّ أحسب الكمية المهدورة من الخشب.
إظهار الحلّإخفاء الحلّ
الأطوال مرتبة تنازليا: 75 70 60 50 35 20 20 20
B_1: 75, 20
B_2: 70, 20
B_3: 60, 35
B_4: 50, 20 عدد الألواح اللازمة خوارزمية الملاءمة الأولى المتناقصة هو 4 ألواح. التكلفة الكلية لصنع الخزانة باستعمال خوارزمية الملائمة الأولى المتناقصة هي: 4 \times 3 = 12\ JD الكمية المهدورة من الخشب هي: 400 - 350 = 50 \ cm - سؤال من الكتاب · صفحة 69تحدّ: في ما يأتي كتل 9 حقائب سفر (إلى أقرب كيلوغرام) يراد نقلها في حاويات، ويمكن لكلّ منها أن تحمل كتلة إجمالية أقصاها 50 kg: 24 14 8 x 19 25 6 17 9 إذا علمت أنّ كتلة إحدى الحقائب لم تقس قياسا دقيقا، ولتكن x كيلوغراما، حيث: 23 ≥ x > 19، أحدّد كيف توزّع الحقائب على الحاويات باستعمال خوارزمية الملائمة الأولى.
إظهار الحلّإخفاء الحلّ
B_1: 24, 14, 8 B_2: x, 19, 6 B_3: 25, 17 B_4: 9 عدد الحاويات اللازمة باستعمال خوارزمية الملاءمة الأولى هو 4 حاويات. - سؤال من الكتاب · صفحة 108شحن: في ما يأتي كتل 10 صناديق (بالكيلوغرام) يراد نقلها في شاحنات، ويمكن لكلّ منها أن تحمل كتلة إجمالية أقصاها 300 kg: | 175 | 135 | 210 | 105 | 100 | 150 | 60 | 20 | 70 | 125 | |---|---|---|---|---|---|---|---|---|---| أحدّد كيف توزّع الصناديق على الشاحنات باستعمال خوارزمية الصندوق الكامل، ثمّ أحدّد عدد الشاحنات اللازمة لذلك باستعمال هذه الخوارزمية.
إظهار الحلّإخفاء الحلّ
B_1: 210, 70, 20, B_2: 175, 125, B_3: 135, 105, 60, B_4: 150, 100 عدد الشاحنات اللازمة باستعمال خوارزمية الصندوق الكامل هو 4 شاحنات. - سؤال من الكتاب · صفحة 69أثقال: يرغب مدرب في صالة رياضية أن يرتب على رفوف الأثقال المبينة كتلتها (بالكيلوغرام) في ما يلي، علما بأنه يمكن لكل رف منها أن يحمل 40 kg في الحد الأقصى: 18 16 24 16 20 10 12 8 16 12 10 4 12 6 13 أحدّد كيف ترتّب الأثقال على الرفوف باستعمال خوارزمية الملاءمة الأولى، ثمّ أحدّد عدد الرفوف اللازمة لذلك باستعمال هذه الخوارزمية.
إظهار الحلّإخفاء الحلّ
B_1: 18, 16, 4
B_2: 24, 16
B_3: 20, 10, 8
B_4: 12, 16, 12
B_5: 10, 12, 6
B_6: 13 عدد الرفوف اللازمة باستعمال خوارزمية الملاءمة الأولى هو 6 رفوف. - سؤال من الكتاب · صفحة 69يراد تعبئة العلب (المعطى ارتفاعاتها في ما يلي) في صناديق، ارتفاع كلّ منها 5 وحدات طول. إذا علمت أنّ للعلب والصناديق المقطع العرضي نفسه، فأجيب عن الأسئلة التالية تباعا:
| 1.8 | 1.4 | 2.6 | 1.6 | 2.8 | 0.9 | 3.1 | 0.8 | 1.2 | 2.4 | 0.6 |
|---|---|---|---|---|---|---|---|---|---|---|
استعملت خوارزمية الملاءمة الأولى لتعبئة العلب في الصناديق، فكان الحل:
B1: 1.8, 1.4, 1.6
B2: 2.6, 0.9, 0.8, 0.6
B3: 2.8, 1.2
B4: 3.1
B5: 2.4
أي أنّ عدد الصناديق المستعملة 5 صناديق.
أجد الارتفاع المهدور في الصناديق جميعها.إظهار الحلّإخفاء الحلّ
الارتفاع المهدور هو 5 \times 5 - 19.2 = 5.8 - سؤال من الكتاب · صفحة 69أثقال: يرغب مدرب في صالة رياضية أن يرتب على رفوف الأثقال المبينة كتلتها (بالكيلوغرام) في ما يلي، علما بأنه يمكن لكل رف منها أن يحمل 40 kg في الحد الأقصى: 18 16 24 16 20 10 12 8 16 12 10 4 12 6 13 أحدّد كيف ترتّب الأثقال على الرفوف باستعمال خوارزمية الصندوق الكامل، ثمّ أحدّد عدد الرفوف اللازمة لذلك باستعمال هذه الخوارزمية.
إظهار الحلّإخفاء الحلّ
B_1: 18, 16, 6
B_2: 24, 16
B_3: 20, 10, 10
B_4: 12, 16, 12
B_5: 8, 4, 12, 13 عدد الرفوف اللازمة باستعمال خوارزمية الصندوق الكامل هو 5 رفوف. - سؤال من الكتاب · صفحة 69تبرير: في ما يأتي أطوال 8 قطع خشبية (بالسنتيمتر) تلزم لصنع خزانة صغيرة، ويراد قصّها من ألواح خشبية: 20 35 50 60 20 70 75 20 تتوافر ألواح خشبية طول كلّ منها 1m وسعرها 3 JD، وألواح خشبية طول كلّ منها 1.5m وسعرها 4 JD. ما أقل تكلفة لصنع الخزانة إذا أمكن استعمال الألواح التي طولها 1m والألواح التي طولها 1.5m معا؟ أبرر إجابتي.
إظهار الحلّإخفاء الحلّ
أقل تكلفة لصنع الخزانة هي 11 JD، وذلك باستعمال لوحين اثنين (الأول والثاني) طول كل منهما 1.5 m والثالث طوله 1 m بالتوزيع الآتي: B_1: 75, 70 B_2: 60, 50, 35 B_3: 20, 20, 20 - سؤال من الكتاب · صفحة 69يراد تعبئة العلب (المعطى ارتفاعاتها في ما يلي) في صناديق، ارتفاع كلّ منها 60 وحدة طول. إذا علمت أنّ للعلب والصناديق المقطع العرضي نفسه، 31 10 38 45 19 47 35 28 12 أستعمل خوارزمية الملاءمة الأولى المتناقصة لتعبئة العلب في الصناديق، ثمّ أحدّد عدد الصناديق اللازمة لذلك.
إظهار الحلّإخفاء الحلّ
1. \frac{31 + 10 + 38 + 45 + 19 + 47 + 35 + 28 + 12}{60} = 4.42 \approx 5 الحد الأدنى من عدد الصناديق اللازمة لتعبئة العلب هو 5 صناديق.
2. الارتفاعات مرتبة تنازليا: 47 45 38 35 31 28 19 12 10
3. B_1: 47, 12 B_2: 45, 10 B_3: 38, 19 B_4: 35 B_5: 31, 28
4. عدد الصناديق اللازمة لتعبئة العلب باستعمال خوارزمية الملاءمة الأولى المتناقصة هو 5 صناديق. - سؤال من الكتاب · صفحة 69أسلاك نحاسية: في ما يأتي أطوال (بالسنتيمتر) لـ 10 قطع يراد قصّها من أسلاك نحاسية، طول كلّ منها 1 m: 58 45 18 55 47 12 63 30 19 42 أحدّد كيف تقصّ القطع باستعمال خوارزمية الملاءمة الأولى المتناقصة، ثمّ أحدّد عدد الأسلاك اللازمة لذلك باستعمال هذه الخوارزمية، ثمّ أجد طول الجزء المهدور من الأسلاك جميعها.
إظهار الحلّإخفاء الحلّ
الأطوال مرتبة تنازليا: 63 58 55 47 45 42 30 19 18 12 B_1: 63, 30 B_2: 58, 42 B_3: 55, 45 B_4: 47, 19, 18, 12 عدد الأسلاك اللازمة باستعمال خوارزمية الملاءمة الأولى المتناقصة هو 4 أسلاك. طول الجزء المهدور هو 4 \times 100 - 389 = 11 cm - سؤال من الكتاب · صفحة 108يراد تعبئة العلب (المعطى ارتفاعاتها في ما يلي) في صناديق، ارتفاع كلّ منها 5 وحدات طول. إذا علمت أنّ للعلب والصناديق المقطع العرضي نفسه، | 2.6 | 0.8 | 2.1 | 1.2 | 0.9 | 1.7 | 2.3 | 0.3 | 1.8 | 2.7 | |---|---|---|---|---|---|---|---|---|---| أيّ الخوارزميات توصلت بها إلى الحلّ الأمثل؟ أبرّر إجابتي.
إظهار الحلّإخفاء الحلّ
\frac{2.7 + 2.6 + 2.3 + 2.1 + 1.8 + 1.7 + 1.2 + 0.9 + 0.8 + 0.3}{5} = 3.28 \approx 4 الحد الأدنى من الصناديق اللازمة هو 4 صناديق. جميع الخوارزميات أوصلتنا إلى الحل الأمثل وهو الحد الأدنى من الصناديق.