Discussion :

[K-you]

Bonjour,

Je suis actuellement en train de résoudre de différentes manières le problème du sac à dos (0-1 Knapsack). J'ai implémenté en C et comparé plusieurs types d'algorithmes répondant à ce problème : un brute force, un glouton, un de programmation dynamique récursive, et un de programmation dynamique séquentielle.

Alors maintenant, je voudrais savoir quel autre type d'algorithme est le plus efficace pour résoudre ce problème. Il y a la méthode branch and bounds, ou encore les algorithmes génétiques, ... Je cherche le plus rapide pour donner une solution exacte.

Pour l'instant je penche vers le branch and bounds. Si quelqu'un a un meilleur type d'algo je suis preneur.

[ToTo13]

Je cherche le plus rapide pour donner une solution exacte.

SI par solution exacte tu veux dire "la meilleure solution", alors il me semble que c'est "le brute force" !!!

[K-you]

Les algorithmes de programmation dynamique sont plus rapides que le brute force bien qu'ils soient plus gourmands en mémoire. Je cherche une autre famille d'algorithme que je n'ai pas déjà expérimenté.

[pseudocode]

Les algorithmes de programmation dynamique sont plus rapides que le brute force bien qu'ils soient plus gourmands en mémoire. Je cherche une autre famille d'algorithme que je n'ai pas déjà expérimenté.

Martello et Toth ont écrit un bouquin la dessus.

Leur algo de type "branch & bound" a longtemps fait référence.

[K-you]

Très intéressant comme bouquin, merci.