مشكلة napsack مع قيود رقم العنصر المطلوبة بالضبط

Question

كيف نحل مشكلة الرنية إذا كان علينا الآن إصلاح عدد العناصر الموجودة في الحرف اليدوية بواسطة $ l $ ؟هذه هي نفس المشكلة (أقصى وزن $ W $ ، كل عنصر لديه قيمة $ v $ والوزن $ W $ )، ولكن يجب عليك إضافة بالضبط $ l $ البند(ق) إلى الكتلة (ومن الواضح أن تحتاج إلى تحسين القيمة الإجمالية للفكرة).

كل الطريقة التي فكرت بها في تنفيذ هذا حتى الآن (البرمجة الديناميكية، القوة الغاشمة) قد أدت إلى فشل أو أوقات حساب مستوى عالمية في الكون.أي مساعدة أو أفكار موضع تقدير.

تحرير: أبحث عن حلول الوقت الزائدي متعدد الحدود

Answer 1

يمكنك تحويل هذه المشكلة إلى مثيل من الحرف. دع $ n $ يكون عدد العناصر، $ v $ يكون الحد الأقصى لقيمة عنصر ونفترض أن كل عنصر يزن على الأكثر $ W $ (وإلا يمكن التخلص منها).

لضمان تحديد ما لا يقل عن $ l $ العناصر:

• إضافة $ n (v + 1) $ إلى قيمة كل عنصر.
• الآن المشكلة تعادل ذلك لتعظيم عدد العناصر المختارة، والعلاقات العاجلة لصالح مجموعة من العناصر بأكبر قيمة إجمالية أصلية، رهنا لقيود الوزن. هناك حل يختار على الأقل $ l $ العناصر IFF الحل الأمثل لديه قيمة من $ n (v +1) L $ .

للتأكد من تحديدها على الأكثر $ l $ العناصر:

• إضافة $ (w + 1) $ إلى وزن كل عنصر.
• إضافة $ l (w + 1) $ إلى $ W $ .
• الآن كل مجموعة فرعية من أكثر من $ L $ العناصر يزن على الأقل $ (l + 1) (w + 1) )= l (w + 1) + (w + 1)> l (w + 1) + w دولار ، وبالتالي غير ممكن. كل مجموعة فرعية من $ l $ العناصر التي لديها وزن إجمالي من $ W $ ، تزن الآن $ l (w + 1) + w $ ، وبالتالي هو ممكن IFF $ W \ LE W $ . مجموعة فرعية مع أقل من $ L $ قد تكون ممكنة حتى لو كان وزنه الإجمالي أكثر من $ W $ $ n (v + 1) l $ .