Niveau logiciels

Efficacité dans les calculs

Posté par
manubac 18-01-12 à 22:36

Bonsoir,

J'ouvre ce topic car je me demande s'il est possible, à partir d'une série de nombres réels positifs, de trouver une partie des nombres de cette série de manière à ce que leur somme vaille un nombre déterminé, sachant que ce nombre déterminé est bien somme de nombres de cette série.

Merci si vous avez une idée; je peux être plus précis s'il le faut.

Posté par re : Efficacité dans les calculs 19-01-12 à 06:14

Bonjour,

S'il y a n nombres réels positifs, le nombre de sous ensembles est 2ⁿ. Chaque sous ensemble est une combinaison. Ainsi le nombre de sous ensembles ayant p nombres est $n\choose p$ .

La recherche de la bonne combinaison peut se faire en parcourant un arbre (ayant 2[sup][/sup] branches)...

Maintenant s'il s'agit d'optimiser les calculs pour éviter d'avoir faire des additions inutiles, il faut sans doute commencer par ordonner les nombres de la série.

Posté par re : Efficacité dans les calculs 19-01-12 à 15:30

Merci pour ta réponse

A propos d'optimisation des calculs, c'est à peu près ce que je cherche à faire oui, et j'ai justement ordonnée les nombres pour cela.

Pour l'arbre, il m'est peut-être utile, mais comment l'utiliser ? Que placer à la racine de l'arbre et ensuite ?

La série (S) de nombres est la suivante, ordonnée :

${\blue11.99}|{\red16.99}|{\blue17.99}|{\red17.99}|{\blue17.99}|{\red19.99}|{\blue19.99}|{\red19.99}|{\blue24.99}|{\red24.99}|{\blue25}|{\red25.99}|{\blue25.99}|{\red26.98}|{\blue27.98}|{\red29.99}|{\blue32.98}|{\red35.99}|{\blue47.98}|{\red48.98}|{\blue62.97}|{\red71.97}|{\blue73.48}|{\red73.49}|{\blue74.96}|{\red82.97}|{\blue89}|{\red103.98}|{\blue184.87}$

Elle comporte 29 nombres et on cherche une sous-série (S') telle qu'elle comporte n nombres dont leur somme vaut 608.92. Si cela peut aider, la somme des nombres de S vaut 1338.45.

Posté par re : Efficacité dans les calculs 19-01-12 à 15:32

Petite erreur d'affichage, la série est :

$\\ {\blue11.99}|{\red16.99}|{\blue17.99}|{\red17.99}|{\blue17.99}|{\red19.99}|{\blue19.99}|{\red19.99}|{\blue24.99}|{\red24.99}|{\blue25}|{\red25.99}|{\blue25.99}|{\red26.98}|{\blue27.98} \\ \\ {\red29.99}|{\blue32.98}|{\red35.99}|{\blue47.98}|{\red48.98}|{\blue62.97}|{\red71.97}|{\blue73.48}|{\red73.49}|{\blue74.96}|{\red82.97}|{\blue89}|{\red103.98}|{\blue184.87}$

merci d'avance pour l'aide que tu peux m'apporter

Posté par re : Efficacité dans les calculs 20-01-12 à 13:33

Bonjour,

J'ai fait des recherches exhaustives. Sauf erreur, il n'est pas possible d'arriver à 608.92.
Le montant le plus proche est 608.86, qu'on obtient de 4 manières essentiellement différentes :

24.99 + 25 + 25.99 + 25.99 + 35.99 + 47.98 + 73.48 + 73.49 + 82.97 + 89 + 103.98 = 608.86
24.99 + 24.99 + 25 + 25.99 + 35.99 + 48.98 + 73.48 + 73.49 + 82.97 + 89 + 103.98 = 608.86
19.99 + 25 + 25.99 + 29.99 + 35.99 + 48.98 + 73.48 + 73.49 + 82.97 + 89 + 103.98 = 608.86
17.99 + 24.99 + 25 + 25.99 + 25.99 + 29.99 + 35.99 + 73.48 + 73.49 + 82.97 + 89 + 103.98 = 608.86

Posté par re : Efficacité dans les calculs 20-01-12 à 21:39

Bonjour

C'est un cas particulier du problème dit "du sac à dos", qui est un grand classique des problèmes d'optimisation en algorithmique.

Ici, ça correspond au cas où le poids de chaque objet est égal à sa valeur, et où on veut un ensemble d'objet de poids exactement égal au poids donné (on fait donc tourner l'algo, et on vérifie à la fin si la solution trouvée est de poids exactement égal).