مشكلة napsack مع القيد
-
29-09-2020 - |
سؤال
أنا على دراية بمشكلة knapsack 0/1. ولكن إذا تم فرض القيد التالي ... كيف يمكنني حل السؤال؟
- إذا اخترت بعض العناصر "U" فلن تتمكن من اختيار عنصر آخر "V".
على سبيل المثال
يتم إعطاء البنود باسم [الاسم والوزن والقيمة]
البنود هي:
10 20
ب 50 80
ج 20 30
د 30 70
E 50 50
إذا اخترت B، فلا يمكنك اختيار A.
إذا اخترت E، فلا يمكنك اختيار C.
إذا اخترت D، فلا يمكنك اختيار A.
بطريقة مماثلة يتم إعطاء القيود.
يرجى تقديم لي طريقة لحل المشكلة أعلاه.أي مساعدة موضع تقدير كبير.
المحلول
يمكنك بسهولة تشفير هذا كإصدار 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 $
على الرغم من ذلك، فليس من الواضح لي أن حامل البرمجة الخطية العصرية سيستفيد بالكامل من هيكل المشكلة. لذلك ربما قد يؤدي حل أكثر تخصصا بشكل أفضل في الممارسة العملية.