Problema da mochila com uma restrição

Question

Eu estou familiarizado com o problema da mochila 0/1. Mas se a seguinte restrição for imposta ... Como resolva a pergunta?

.
1. Se você escolher algum item 'u', você não poderá escolher outro item 'v'.

por exemplo Itens são dados como [nome, peso, valor]
Itens são:
A 10 20
B 50 80
C 20 30
D 30 70
E 50 50


Se você escolher B, você não pode escolher A.
Se você escolher e, então você não pode escolher C.
Se você escolher d, então você não pode escolher A.
Da maneira semelhante, as restrições são dadas.


Por favor, me forneça alguma maneira de resolver o problema acima.Qualquer ajuda é muito apreciada.

Answer 1

As abordagens de programação dinâmica padrão provavelmente não vão funcionar para esse problema, porque o extra "isto ou isso, mas não ambos", destroem o Subproblemas sobrepostos Propriedade. Então vamos explodir a marreta.

Você pode acará-lo facilmente como um 0-1 Integer Linear Programming Problema e use um problema solucionador off-the-prateleira. Para o exemplo dado (e algum limite máximo de peso $ W $ ), um problema de 0-1 adequado é:

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

Embora, não seja óbvio para mim que um solucionador de programação linear inteiro aproveitará ao máximo a estrutura do problema. Então talvez uma solução mais especializada possa ter uma melhor prática.