Optimisation de somme

Bonjour,

Je ne sais pas si une formule mathématique existe mais le probleme est le suivant :

J'ai une série de chiffre :
( 25 - 17 - 15 - 14 - 14 - 12 - 10 - 5 - 3 - 2 - 2 - 1)

le but est d'arriver à faire le moins de somme possible sachant que les sommes ne doit pas dépasser le nombre max de 30.

Exemple

Resutat non optimisé
1 25 + 5 = 30
2 17 + 12 + 1 = 30
3 15 + 14 = 29
4 14 + 10 + 3 + 2 = 29
5 2

Resutat optimisé
1 17 + 3 + 10 = 30
2 15 + 14 + 1 = 30
3 25 + 5 = 30
4 14 + 12 + 2 + 2 = 30


Algo ou formule math ??

bonjour
je ne pense pas qu'on puisse résoudre ça parfaitement sans un algo de parcours d'arbre (l'arbre des partitions d'un ensemble serait le mieux mais je ne sais pas s'il est facile à programmer...)

Avec un algo génétique tu peux arriver à trouver la solution assez facilement, mais le codage est assez contraignant.

J'ai déjà codé un algo de ce genre, en ADA, le but était assez similaire : on dispose d'une liste de chansons (chaque chanson ayant une durée propre), et on essaie de créer une compilation de 5 CD en perdant le moins de place possible, et au bout de 5000 ou 10000 générations j'arrivais à des solutions parfaites.

Si ca t'interresse, je chercherais ce soir pour voir si je le retrouve...

MarneusCalgarXP si c'est un algo non genetiquement modifié pourquoi pas oui. ;)
Le probleme des chansons est effectivement similaire et pratique !

Sinon, acx01b, C'est quoi un arbre des partitions d'un ensemble ?

Erf, impossible de retrouver l'archive, elle date un peu :(

KNAPSACK

MarneusCalgarXP
Ok dommage que tu l ais perdu pour tes futurs compils.

pseudocode
J'ai vu le prob du Knapsack.
Ca me parait différent car une seule somme et deux notions (poids prix) mais il doit y avoir un début de réponse.
Je vais voir ce que je peux en faire...

Citation:

---

Envoyé par jeffciara

J'ai vu le prob du Knapsack.
Ca me parait différent car une seule somme et deux notions (poids prix) mais il doit y avoir un début de réponse.
Je vais voir ce que je peux en faire...

---

Citation:

---

Envoyé par wikipedia

Knapsack-like problems:

If we have a number of containers (of the same size), and we wish to pack all n items in as few containers as possible, we get the bin packing problem

---

Oui c'est bien celui ci le problème : bin packing problem
Maintenant qu'il porte un nom je vais pouvoir être appelé à le résoudre...
Je vais quand même vérifier si il existe un algo sur le net.

Citation:

---

Envoyé par jeffciara

Algo ou formule math ??

---

Pas de bol, mais ton problème est NP-complet :-) Autrement dit, tu n'as (presque ;-)) aucune chance de trouver un algo qui ne soit pas polynomial (en gros, tester toutes les possibilités !) Après, il est possible que tu puisses trouver un algo qui soit meilleurs dans certain cas, ou encore un algo approché. En revanche, si tu trouves un algo polynomial exacte, ne le donne pas ici, il vaut un million de dollars :-)

Citation:

---

Envoyé par alex_pi

En revanche, si tu trouves un algo polynomial exacte, ne le donne pas ici

---

C'est clair. Envoie le moi par mail ;)

J'ai toujours pas retrouvé mon algo, mais un pote de la fac m'a envoyé le sien, je te le file ici.

En revanche, je n'ai pas testé s'il arrivait à des solutions parfaites ou pas :lol:
En tous cas, y'a une doc qui explique le principe global de l'algo...

Le voici: Pièce jointe 17490

Citation:

---

Envoyé par alex_pi

Pas de bol, mais ton problème est NP-complet :-) Autrement dit, tu n'as (presque ;-)) aucune chance de trouver un algo qui ne soit pas polynomial (en gros, tester toutes les possibilités !) Après, il est possible que tu puisses trouver un algo qui soit meilleurs dans certain cas, ou encore un algo approché. En revanche, si tu trouves un algo polynomial exacte, ne le donne pas ici, il vaut un million de dollars :-)

---

exponentiel a la place de la premiere occurence de polynomial

A noter qu'un bete algo glouton fonctionne generalement bien. (Si j'ai bonne memoire, il ne fait jamais plus de 50% pire que la solution optimale).

Ouais pour le knap sack, tu peux trouver des solutions approchés de l'optimal.
L'algo est simple :
tu tries ta liste de nombre en ordre décroissant, tu prend le premier element et tu l'additionne avec les suivants jusqu'à être le plus proche de 30 et dès que le nombre suivant a ta somme ne permet pas de l'ajouter, tu le passes et tu essayes avec l'elem suviant jusqu'a arriver a la fin de ta liste. (tu as fais ta premiere somme)
Et maintenant tu répète la même chose pour une prochaine somme et ainsi de suite.
Si mes souvenirs sont bon, c'est un des meilleurs algo pour ce probleme
(bien sur il y a surement des optimisations :roll: