Sac à dos avec éléments à considérer

Question

J'ai les articles I1, I2, I3, I4 avec les poids W1 ... W4 et les valeurs V1 ... V4. Je veux maximiser les valeurs avec des poids minimums. C'est un sac à dos traditionnel. Cependant, il y a une petite contrainte que certains éléments ne peuvent pas aller ensemble. Alors disons que I2 et I3 ne peuvent pas aller ensemble. Quelqu'un peut-il fournir une solution de programmation dynamique ou toute autre solution pour le même.

Answer 1

Avec cette contrainte, le problème devient fortement (contrairement au sac à dos discret, qui n'est que faiblement NP-difficile) NP-difficile. Supposons que tous vos articles ont un poids 1 et la valeur 1.

Décider si vous pouvez obtenir la valeur k (hypothèse où la capacité havresac> = k) est équivalent à trouver k éléments qui ont aucune contrainte entre eux. C'est un problème NP-difficile connu: independent set.

Cela peut être plus facile si vous avez des connaissances supplémentaires sur la nature des contraintes.