إثبات خوارزمية الجشع المستخدمة لتغيير مشكلة التعبئة بن

Question

يتم إعطاؤنا مجموعة من الأوزان $ W $ (جميع الأوزان أعداد صحيحة إيجابية)، ونحن بحاجة إلى وضع الأوزان داخل الصناديق.يمكن أن يحمل كل صندوق بحد أقصى MAX_VAL، ويكون كل وزن على الأكثر max_val.الاختلاف هو أنه لا ينبغي تغيير ترتيب الأوزان، وهذا هو، يجب أن تكون $ W_I $ داخل صندوق قبل $يتم إدراج W_J $ ، لجميع $ i .

بالنسبة لبيان المشكلة هذه، يمكننا بشكل حدسي أن نرى أن النهج الجشع من ملء صندوق حتى يتم الوصول إلى القيمة القصوى وخلق صندوق جديد لمزيد من الأوزان سينتج الحد الأدنى لعدد الصناديق.أنا غير قادر على التوصل إلى دليل رسمي على أن الحل الجشع هو الأمثل.أي تلميحات أو إرشادات ستكون رائعة!

Answer 1

دع $ g $ يكون الحل الناتج عن الخوارزمية الجشع. لكل حل آخر $ S $ ، دع $ i (s) $ يكون مؤشر الوزن الأول عند $ S $ تباعد من $ g $ . دع $ o $ يكون الحل الأمثل تعظيم $ i (o) $ . هكذا $ G $ الأماكن $ i (o) $ في bin $ J $ (بالنسبة لبعض $ J $ )، و $ O $ الأماكن < span class="حاوية الرياضيات"> $ i (o) $ في bin $ j + 1 $ . إذا نقلنا $ i (o) $ to bin $ J $ (وهو ممكن منذ $ O $ )، نحصل على حل $ O '$ يستخدم على الأكثر كثافة أكبر عدد أكبر من الصناديق="حاوية الرياضيات"> $ O $ ، وتلبية $ i (o ')> i (o) $ . هذا يتناقض مع اختيار $ O $ .

إذا حاولنا تشغيل هذه الوسيطة على خوارزمية التعبئة BIN غير المقيدة، فسوف نواجه مشكلة عند نقل $ i (o) $ to bin $ j $ قد تكون محتلة عناصر أخرى، وليس ترك مجالا كافيا ل $ i (o) $ . في البديل الذي تفكر فيه، لا يمكن أن يحدث هذا.