Verpackungsproblem mit einer Einschränkung

Question

Ich bin mit 0/1 Rucksackproblem vertraut. Aber wenn die folgende Einschränkung auferlegt ist ... Wie löste ich die Frage?

.
1. Wenn Sie ein Element 'U' wählen, können Sie keinen anderen Element 'V' wählen.

zum Beispiel Artikel werden als [Name, Gewicht, Wert] angegeben
Artikel sind:
A 10 20
B 50 80
C 20 30
D 30 70
E 50 50


Wenn Sie b wählen, können Sie sich nicht auswählen.
Wenn Sie E wählen, können Sie nicht C-C.
wählen Wenn Sie d wählen, dann können Sie keine A-A-A-Code auswählen.
In ähnlicher Weise sind die Einschränkungen angegeben.


Bitte geben Sie mir einen Weg, um das obige Problem zu lösen.Jede Hilfe wird sehr geschätzt.

Answer 1

Standard-dynamische Programmieransätze werden wahrscheinlich nicht für dieses Problem funktionieren, da das Extra "dieses oder das, aber nicht beide" die Einschränkungen die überlappende Unterprobleme Eigenschaft. Also brechen wir den Vorschlaghammer aus.

Sie können dies problemlos als 0-1 integer lineare Programmierung problemieren und verwenden Off-the-Shelf-Solver. Für das angegebene Beispiel (und einige maximale Gewichtsgrenze $ W $ ) ist ein geeignetes 0-1-ILP-Problem:

maximieren $ 20A + 80B + 30C + 70D + 50E $

Vorbehaltlich
$ 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 $

Obwohl es mir nicht offensichtlich ist, dass ein ganzgerechter linearer Programmierlöser die Struktur des Problems voll nutzen wird. So kann vielleicht eine spezialisierte Lösung in der Praxis besser funktionieren.