Problema de mochila con una restricción

Question

Estoy familiarizado con 0/1 problema de mochila. Pero si se impone la siguiente restricción ... ¿Cómo resuelvo la pregunta?

1. Si elige un elemento 'u' no podrás elegir otro elemento 'v'.

por ejemplo Los artículos se dan como [nombre, peso, valor]
Los artículos son:
Un 10 20
B 50 80
C 20 30
D 30 70
E 50 50


Si elige B, entonces no puede elegir A.
Si elige e, entonces no puede elegir C.
Si elige D, entonces no puede elegir A.
De la manera similar, se dan las restricciones.


Por favor, proporcione algo de alguna manera de resolver el problema anterior.Cualquier ayuda es muy apreciada.

Answer 1

Es probable que los enfoques de programación dinámica estándar no funcionen para este problema, ya que las restricciones adicionales "esto o que no ambas" destruyen el subproblemes superpuestos propiedad. Así que vamos a romper el martillo.

Puede codificar esto fácilmente como una 0-1 Integer Linear Programming problema y uso un problema Solucionador fuera del estante. Para el ejemplo dado (y algunos límites de peso máximo $ w $ ), un problema de ILP de 0-1 adecuado es:

maximizar $ 20A + 80B + 30C + 70D + 50E $
Sujeto 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 $

Aunque, no es obvio para mí que un solvente de programación lineal entero aproveche al máximo la estructura del problema. Así que quizás una solución más especializada puede desempeñarse mejor en la práctica.