0-1 à Dos algorithme

Est la suivante sac à Dos 0-1 problème résoluble:

  • 'float' valeurs positives et
  • 'float' poids (qui peut être positif ou négatif)
  • "flotter", la capacité du sac-à-dos > 0

J'ai en moyenne < 10 articles, donc je suis en train de penser à l'aide d'une force brute de la mise en œuvre. Cependant, je me demandais si il ya une meilleure façon de le faire.

Avez-vous vraiment dire possible ou résoluble efficacement?
Si vous n'avez pas besoin d'une réponse exacte, vous devriez regarder dans le recuit simulé..
2^10 est de 1024. Certainement la force brute, même si il ya une "meilleure façon", il sera presque certainement beaucoup plus lent.
Alors, quelle est la différence entre les "valeurs positives" et le "poids"? Qu'est-ce que vous essayez de frapper?
Chaque élément a une valeur et un poids. Nous voulons maximiser la somme des valeurs telles que la somme des poids est <= sac-à-dos de la capacité.

OriginalL'auteur alhazen | 2011-11-14