الصناديق المستخدمة
الحد الأدنى
أقل عدد ممكن

      أوزان العناصر (كغ)

        مزيد عن مسألة تعبئة الصناديق

        مسألة تعبئة الصناديق

        طرود في شاحنات، وملفات على أقراص، ومهام على آلات: تسأل مسألة تعبئة الصناديق كيف نضع قائمة من العناصر في أقل عدد ممكن من الصناديق المتساوية. لا تُعرف طريقة سريعة تجد دائمًا أفضل تعبئة، لكن القواعد البسيطة تقترب منها. اختر قاعدة، وتتبّعها خطوة بخطوة، وقارنها بالإجابة الدقيقة. انقر عنصرًا على الرف، ثم انقر صندوقًا لتضعه فيه: الصناديق الخضراء فيها متسع له، و«صندوق جديد» يفتح صندوقًا آخر. انقر عنصرًا في صندوق لتخرجه مرة أخرى. عبّئ كل العناصر في أقل عدد ممكن من الصناديق؛ يبيّن الحد الأدنى (الوزن الكلي مقسومًا على حجم الصندوق، مقرّبًا إلى الأعلى) وأقل عدد ممكن مدى قربك، ويعرض «أقل عدد من الصناديق» أفضل تعبئة. غيّر أوزان العناصر (بالكيلوغرام) وحجم الصندوق في اللوحة. يعرض عرض «خطوة بخطوة» كيف تعبّئ القواعد السريعة: الملاءمة التالية أو الملاءمة الأولى أو أفضل ملاءمة، على العناصر بالترتيب الذي كُتبت به أو مرتبة من الأكبر إلى الأصغر، أو الإجابة الدقيقة التي تجدها البرمجة الديناميكية. اضغط «تشغيل» لتشاهد العناصر تدخل الصناديق، أو «خطوة» و«رجوع» للتقدم خطوة بخطوة، واسحب شريط الخطوات للانتقال إلى أي موضع. عند تحديد منطقة التعبئة، تتقدم مفاتيح الأسهم خطوة، ويشغّل مفتاح المسافة ويوقف مؤقتًا، وينقل Home وEnd إلى البداية والنهاية.

        كيف يعمل

        1. انقر على غرض، ثم انقر على صندوق فيه مكان لتضعه فيه، أو على «صندوق جديد» لفتح صندوق آخر.
        2. حاول استخدام أقل عدد ممكن من الصناديق، أو اضغط «أقل عدد من الصناديق» لرؤية أفضل تعبئة.
        3. افتح عرض «خطوة بخطوة»، واختر قاعدة، واضغط «تشغيل» لتشاهد كل غرض وهو يجرّب الصناديق.

        القواعد

        الملاءمة التالية تُبقي الصندوق الأخير وحده مفتوحًا: العنصر الذي لا يتسع له يبدأ صندوقًا جديدًا. الملاءمة الأولى تجرّب الصناديق بدءًا من الأول وتأخذ أول صندوق فيه متسع. أفضل ملاءمة تجرّب كل الصناديق وتأخذ أكثرها امتلاءً من بين ما فيه متسع، فتترك أقل مساحة غير مستخدمة. ويمكن للملاءمة الأولى وأفضل ملاءمة أيضًا أن ترتّبا العناصر أولًا من الأكبر إلى الأصغر، فينتج عن ذلك الملاءمة الأولى التنازلية وأفضل ملاءمة تنازلية.

        الإجابة الدقيقة

        القاعدة الأخيرة ليست قاعدة تقريبية: فهي تجد أقل عدد من الصناديق بالبرمجة الديناميكية على مجموعات العناصر. لكل مجموعة من العناصر تحفظ أقل عدد من الصناديق يتسع لها، ومن بين التعبئات التي تستخدم هذا العدد، أصغر حمولة في الصندوق الأخير. تكبر المجموعة عنصرًا واحدًا في كل مرة، وهذا العنصر إما يُضاف إلى الصندوق الأخير أو يفتح صندوقًا جديدًا. مع n عنصر توجد 2ⁿ مجموعة، ولهذا لا يسمح التطبيق بأكثر من 12 عنصرًا. والحد الأدنى، أي الحجم الكلي مقسومًا على حجم الصندوق ومقرّبًا إلى الأعلى، يبيّن مدى قرب التعبئة من الأفضل.

        الأسئلة المتداولة

        ما أفضل قاعدة لتعبئة الصناديق؟

        من بين القواعد السريعة، الملاءمة الأولى التنازلية وأفضل ملاءمة تنازلية هما الأقوى: لا تستخدمان أبدًا أكثر من 11/9 من أقل عدد من الصناديق، زائد ثابت صغير. أما الملاءمة الأولى وأفضل ملاءمة على عناصر غير مرتبة فتبقيان في حدود 1.7 ضعف أقل عدد من الصناديق، والملاءمة التالية في حدود ضعفين.

        لماذا تعبئة الصناديق صعبة؟

        مجرد تحديد ما إذا كانت العناصر تتسع في صندوقين فقط هو بالفعل مسألة التقسيم، وهي NP-كاملة. لذا ما لم يكن P = NP، فلا توجد طريقة تجد أقل عدد من الصناديق بسرعة لكل مدخل، والطرق الدقيقة تستغرق وقتًا أُسّيًا في أسوأ الحالات.

        ما الحد الأدنى؟

        الحجم الكلي للعناصر مقسومًا على حجم الصندوق ومقرّبًا إلى الأعلى. لا يمكن لأي تعبئة أن تستخدم صناديق أقل، لأن الصناديق يجب أن تتسع لكل العناصر. وكثيرًا ما تساويه أفضل تعبئة، ولكن ليس دائمًا: ثلاثة عناصر حجم كل منها 6 مع صناديق حجمها 10 حدها الأدنى 2، لكنها تحتاج إلى 3 صناديق.

        هل هذه برمجة ديناميكية؟

        الإجابة الدقيقة كذلك: فهي تبني أفضل تعبئة لكل مجموعة من العناصر من أفضل تعبئات المجموعات الأصغر. أما القواعد السريعة فهي طرق جشعة، تقرر مرة واحدة ولا تعود إلى الوراء أبدًا.

        هل يُرسَل أي شيء إلى أي مكان؟

        لا. كل شيء يُحسب في متصفحك، وتبقى آخر إعداداتك في التخزين المحلي لهذا المتصفح.

        هل أنت مستعد لتجربتها؟

        افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

        الانتقال إلى المحرر