مشكلة napsack مع القيد

Question

أنا على دراية بمشكلة knapsack 0/1. ولكن إذا تم فرض القيد التالي ... كيف يمكنني حل السؤال؟

1. إذا اخترت بعض العناصر "U" فلن تتمكن من اختيار عنصر آخر "V".

على سبيل المثال يتم إعطاء البنود باسم [الاسم والوزن والقيمة]
البنود هي:
10 20
ب 50 80
ج 20 30
د 30 70
E 50 50


إذا اخترت B، فلا يمكنك اختيار A.
إذا اخترت E، فلا يمكنك اختيار C.
إذا اخترت D، فلا يمكنك اختيار A.
بطريقة مماثلة يتم إعطاء القيود.


يرجى تقديم لي طريقة لحل المشكلة أعلاه.أي مساعدة موضع تقدير كبير.

Answer 1

من المحتمل أن تكون أساليب البرمجة الديناميكية القياسية من المحتمل ألا تعمل من خلال هذه المشكلة، لأن "هذا أو ذلك ولكن ليس كلا" القيود تدمير متداخل المشاكل الفرعية الخاصية. لذلك دعونا نفط القذرة القذرة.

يمكنك بسهولة تشفير هذا كإصدار 0-1 البرمجة الخطية عدد صحيح مشكلة واستخدام خارج الجرف الحلال. للحصول على المثال المحدد (وبعض الحد الأقصى للحد من الوزن $ W $ )، مشكلة مناسبة 0-1 ILP هي:

تعظيم $ 20A + 80B + 30C + 70D + 50E $
تخضع لل $ a، b، c، d، e \ in \ {0، 1 \} $
$ 10a + 50B + 20C + 30E + 50E \ LE W $
$ a + b \ le 1 $
$ c + e \ le 1 $
$ a + d \ le 1 $

على الرغم من ذلك، فليس من الواضح لي أن حامل البرمجة الخطية العصرية سيستفيد بالكامل من هيكل المشكلة. لذلك ربما قد يؤدي حل أكثر تخصصا بشكل أفضل في الممارسة العملية.