Проблема Knaxackack с ограничением

Question

Я знаком с проблемой 0/1 knaxack. Но если навязано следующее ограничение ... Как решить вопрос?

1. Если вы выберете элемент «U», вы не сможете выбрать другой элемент «V».

Например Предметы даны как [имя, вес, значение]

Предметы:

10 20
B 50 80
C 20 30
D 300 70
E 50 50


Если вы выберете B, то вы не можете выбрать A.

Если вы выберете e, то вы не можете выбрать C.
Если вы выберете D, то вы не можете выбрать A.

Точно так же, как ограничения даны.


Пожалуйста, предоставьте мне какой-то способ решить вышеупомянутую проблему.Любая помощь высоко ценится.

Answer 1

Стандартные динамические программированные подходы, вероятно, не будут работать на эту проблему, потому что дополнительный «это или то, но не оба« ограничения уничтожат Перекрывающиеся подпункты недвижимость. Итак, давайте раскроем кувалду.

Вы можете легко кодировать это как a 0-1 целочисленное линейное программирование Проблема и используйте Solf-Shelf Solver. Для данного примера (и какой-то максимальный предел веса $ W $ ), подходящий 0-1 проблема ILP:

Максимизация $ 20A + 80b + 30c + 70d + 50e $
При условии

$ a, b, c, d, e \ in \ {0, 1 \} $

$ 10A + 50b + 20c + 30d + 50e \ le w $
$ a + b \ le 1 $
$ c + e \ le 1 $
$ a + d \ le 1 $

Хотя для меня не очевидно, что целочисленное линейное программирование воспользуется полным преимуществом структуры проблемы. Поэтому, возможно, более специализированное решение может работать лучше на практике.