2010-10-19 9 views
1

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.Sac à dos avec éléments à considérer

+0

N'importe quel autre endroit sur Internet (ou dans un livre de texte) peut fournir une solution? Un peu difficile à croire ... –

Répondre

2

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.