# Problème d'optimisation

**URL:** <https://forum.geekzone.fr/t/probleme-doptimisation/9621>\
**Category:** Dev\
**Created:** [Juillet 16, 2003, 7:24 UTC](https://forum.geekzone.fr/t/probleme-doptimisation/9621 "2003-07-16T07:24:03Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![Gimly](https://forum.geekzone.fr/user_avatar/forum.geekzone.fr/gimly/32/146_2.png) [@Gimly](https://forum.geekzone.fr/u/Gimly)\
**Post date:** [Juillet 16, 2003, 7:24 UTC](https://forum.geekzone.fr/t/probleme-doptimisation/9621/1 "2003-07-16T07:24:03Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![prepa](https://forum.geekzone.fr/letter_avatar_proxy/v4/letter/p/ed655f/32.png) [@prepa](https://forum.geekzone.fr/u/prepa)\
**Post date:** [Juillet 16, 2003, 7:41 UTC](https://forum.geekzone.fr/t/probleme-doptimisation/9621/2 "2003-07-16T07:41:46Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![xentyr](https://forum.geekzone.fr/user_avatar/forum.geekzone.fr/xentyr/32/29_2.png) [@xentyr](https://forum.geekzone.fr/u/xentyr)\
**Post date:** [Juillet 16, 2003, 8:09 UTC](https://forum.geekzone.fr/t/probleme-doptimisation/9621/3 "2003-07-16T08:09:23Z")

</div>

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

Max(c1.x1+c2.x2+...+cn.xn) avec&nbsp;p1.x1+p2.x2+... +pn.xn&nbsp;\<= 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

---

<div class="post-metadata">

**Author:** ![Moktar](https://forum.geekzone.fr/user_avatar/forum.geekzone.fr/moktar/32/134124_2.png) [@Moktar](https://forum.geekzone.fr/u/Moktar)\
**Post date:** [Juillet 16, 2003, 8:31 UTC](https://forum.geekzone.fr/t/probleme-doptimisation/9621/4 "2003-07-16T08:31:31Z")

</div>

Tiens, un petit lien sur les [algos](http://www.nist.gov/dads/) que j’ai choppé hier. Ca peut éviter de réinventer la roue ![]().

---

<div class="post-metadata">

**Author:** ![xentyr](https://forum.geekzone.fr/user_avatar/forum.geekzone.fr/xentyr/32/29_2.png) [@xentyr](https://forum.geekzone.fr/u/xentyr)\
**Post date:** [Juillet 16, 2003, 8:47 UTC](https://forum.geekzone.fr/t/probleme-doptimisation/9621/5 "2003-07-16T08:47:23Z")

</div>

Tu as une soluce [ici](http://www.ub.rug.nl/eldoc/som/a/01A64/01a64.pdf)&nbsp;qui a l’air bien expliquée (théorie, algo, tests)&nbsp;mais je ne&nbsp;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

---

<div class="post-metadata">

**Author:** ![Gimly](https://forum.geekzone.fr/user_avatar/forum.geekzone.fr/gimly/32/146_2.png) [@Gimly](https://forum.geekzone.fr/u/Gimly)\
**Post date:** [Juillet 16, 2003, 11:05 UTC](https://forum.geekzone.fr/t/probleme-doptimisation/9621/6 "2003-07-16T11:05:39Z")

</div>

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 ![]()