Problema di zaino con un vincolo

Question

Ho familiarità con il problema dello zaino 0/1. Ma se è imposto il seguente vincolo ... Come risolvo la domanda?

.
1. Se scegli un po 'di elemento' u 'non sarai in grado di scegliere un altro elemento "v".

Ad esempio Gli articoli sono dati come [nome, peso, valore]
Gli articoli sono:
A 10 20
B 50 80
C 20 30
D 30 70
E 50 50


Se si sceglie B, allora non puoi scegliere A.
Se scegli e allora non puoi scegliere C.
Se scegli D, allora non puoi scegliere A.
Nel modo simile vengono forniti i vincoli.


Si prega di fornire un modo per risolvere il problema di cui sopra.Qualsiasi aiuto è molto apprezzato.

Answer 1

Gli approcci di programmazione dinamica standard non funzionano probabilmente per questo problema, poiché il "Vuoto", ma non entrambi "i vincoli distruggono il subproblems sovrapposti proprietà. Quindi scoppiamo il mazzetto.

Puoi facilmente codificarlo come un 0-1 Programmazione lineare integrante Problema e usa un problema Solver off-the-shelf. Per l'esempio dato (e un limite massimo di peso $ W $ ), un problema di 0-1 ilp adatto è:

Maximize $ 20A + 80b + 30c + 70d + 50e $
Soggetto a
. $ 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 $

Sebbene, non è evidente per me che un solver di programmazione lineare intero sfrutterà appieno la struttura del problema. Quindi forse una soluzione più specializzata può funzionare meglio nella pratica.