Problème d'optimisation

Salut à tous,
j’ai reçu un problème que je dois rendre avant dimanche, c’est de la programmation. Le problème c’est que je ne vois pas du tout comment partir, j’arrive pas bien à voir quel algorithme je pourrais utiliser pour coder ça… mise à part tester toutes les solutions, mais ça prendrait bien trop de temps. Pourriz-vous me filer un chtit coup de pouce?

En gros l’idée c’est de choisir parmis n boîtes contenant une certaine somme d’argent et ayant un poid X celle permettant de maximiser la somme d’argent sans que la somme de poids dépasse un certain chiffre.
Il ne faut pas que l’algorithme dépasse les 20 secondes de calcul… donc la méthode brute force me paraît pas des mieux choisie… si qqn a une idée?

je n’ai pas le temps de développer, mais c’est le problème connu en optimisation combinatoire sous le nom de problème du sac à dos… On le resolvait par un algorithme de branch & bound, mais la complexité reste grosse ( c’est une énumération un peu améliorée). Sinon, il y a des heuristiques pas trop mal

C’est un problème d’optimisation de nombres entiers avec contrainte :

Max(c1.x1+c2.x2+...+cn.xn) avec p1.x1+p2.x2+... +pn.xn <= P
où x1,...,xn € {0,1}, c1,...,cn sont les coûts associés aux items 1 à n, et p1,...pn leur poids.

Cherche Binary Knapsack Problem sur google

PS : Glop, tu peux rajouter et comme balises ?

Ce message a été édité par xentyr le 16/07/2003

Tiens, un petit lien sur les algos que j’ai choppé hier. Ca peut éviter de réinventer la roue .

Tu as une soluce ici qui a l’air bien expliquée (théorie, algo, tests) mais je ne sais pas si elle est optimale (je l’ai survolée). À toi de voir si ça rentre dans les critères qu’on t’a donnés (à savoir <20 sec. de calcul mais c’est un peu vague)
Ce message a été édité par xentyr le 16/07/2003

OKi, je vous remercie infiniment!
Je vais essayer de comprendre tout ça…
A première vue ça a l’air plutôt bien prise de tête, mais bon c’est intéressant!

Je suis toujours aussi impressioné par la rapidité de réponse de ce forum lol