0/1 Sac à dos avec peu de variables: quel algorithme?

Question

Je dois implémenter la solution à un problème Knapsack 0/1 avec des contraintes. Mon problème aura dans la plupart des cas quelques variables (~ 10-20, au plus 50). Je rappelle de l'université qu'il existe un certain nombre d'algorithmes qui dans de nombreux cas fonctionnent mieux que la force brute (je pense, par exemple, à un algorithme de branchement et de liaison). Puisque mon problème est relativement petit, je me demande s'il y a un avantage appréciable en termes d'efficacité lorsqu'on utilise une solution sophistiquée par opposition à la force brute. Si cela aide, je suis en train de programmer en Python.

Answer 1

Les trucs de force brute fonctionneraient correctement pour 10 variables, mais pour, disons, 40 vous obtiendriez quelque 1000'000'000'000 solutions possibles, ce qui serait probablement trop long à énumérer. Je considérerais des algorithmes approximatifs, par ex. l'algorithme de temps polynomial (voir, par exemple, http://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf) ou utiliser un algorithme de recherche tel que branch-and-bound, peut-être avec une heuristique supplémentaire.

Answer 2

Vous pouvez utiliser un algorithme pseudo-polynomial, qui utilise la programmation dynamique, si la somme des poids est suffisamment petite. Vous calculez simplement si vous pouvez obtenir le poids X avec les premiers éléments Y pour chaque X et Y. Cela s'exécute dans le temps O (NS), où N est le nombre d'éléments et S est la somme des poids.

Une autre possibilité consiste à utiliser une approche de "meet-in-the-middle". Divisez les éléments en deux moitiés et: Pour la première moitié, prenez toutes les combinaisons possibles d'éléments (il y a 2^(N/2) combinaisons possibles dans chaque moitié) et stockez son poids dans un ensemble. Pour la seconde moitié, prendre toutes les combinaisons possibles et vérifier s'il existe une combinaison en première moitié avec un poids approprié. Cela devrait fonctionner en O (2^(N/2)) fois.

Answer 3

Les algorithmes de force brute retourneront toujours les meilleures solutions. Le problème avec eux est que dans les problèmes d'ordre exponentiel, ils deviennent rapidement impossibles.

Si vous avez la garantie d'avoir jusqu'à 20 variables, vous ne testerez pas plus de 1 million de solutions (2^20 = 1M). Par conséquent, la force brute est réalisable et aucun autre algorithme ne renverra une meilleure solution.

Heuristiques sont bonnes, mais ils ne devraient être utilisés que lorsque nous n'avons pas de solution exacte au problème. Il y a un bon livre qui pourrait vous aider: How to Solve it, by Michalewicz.