Problème de sacs à dos avec une contrainte

Question

Je suis familière avec le problème du knapacks 0/1. Mais si la contrainte suivante est imposée ... Comment résoudre la question?

1. Si vous choisissez un élément 'U', vous ne pourrez pas choisir un autre article 'V'.

Par exemple Les articles sont donnés en tant que [nom, poids, valeur]
Les articles sont:
Un 10 20
B 50 80
C 20 30
D 30 70
E 50 50


Si vous choisissez B, alors vous ne pouvez pas choisir A.
Si vous choisissez E, vous ne pouvez pas choisir C.
Si vous choisissez d, vous ne pouvez pas choisir A.
De la même manière, les contraintes sont données.

S'il vous plaît me fournir un moyen de résoudre le problème ci-dessus.Toute aide est très appréciée.

Answer 1

Les approches de programmation dynamique standard ne vont probablement pas fonctionner pour ce problème, car les contraintes supplémentaires "celles-ci ou non à la fois" détruisent le Superposition de sous-émérules . Alors dissipons le Sledgehammer.

Vous pouvez facilement encoder cela comme un 0-1 Programmation linéaire entier problème et utiliser un solveur de stockage hors tension. Pour l'exemple donné (et une limite de poids maximale $ w $ ), un problème approprié 0-1 ILP est le suivant:

optimiser $ 20A + 80B + 30c + 70D + 50e $
Sous réserve de
$ 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 $

Bien que, il n'est pas évident pour moi qu'un solveur de programmation linéaire entier profitera pleinement de la structure du problème. Donc peut-être une solution plus spécialisée peut être meilleure dans la pratique.