Discussion :

[diam's]

voilà le cas :
j'ai des longueurs (de câble, de tubes) déterminés.
J'achète ce cable / tube par couronnes ou tourets de longueurs déterminé

J'aimerais trouver l'algo qui me permettrait d'affiner le débit économique de mes coupes, sachant que les chutes inférieures à 50 m sont inutilisables, d'ou perte de temps et d'argent. Actuellement, je fais cela à la main de façon empirique (au feeling).

Exemple :
longueur des coupes : 118 , 101, 92 , 73, 85, 57 m
Conditionnement : couronne 240 m
Solution couronne 1 : 118 + 101 - reste 21 m (inutilisable)
Solution couronne 2 : 92 + 85 + 57 - reste 6 m (inutilisable)
Solution couronne 3 : 73 - reste 167 m (réutilisable)
Dans ce cas, la longueur inutilisable la plus grande est de 21 m, ce qui est encore correct. Mais cela peut parfois être 40 m.

Si quelqu'un avait une idée...
PS : je suis toujours aussi mauvais en math

[méphistopheles]

Avec peu de solutions comme-ça, tu pourrais toutes les tester, mais si il y en à plus (appelons ce nombre n)
tu pourrais par exemple faire un arbre dont tu explore le début de chaque branche, en regardant les (D-P) (ou D est le nombre de possibilités et P la profondeur) qui sont les moins couteuses (en comptant en terme de pertes.) (pas besoin de regarder les autres, comme tu peux le faire dans n'importe quelle sens, les autres seront des doublets)
par exemple, en listant les longueur non utilisé, tu met la condition: toute chute < la plus petite longueur utilisé est compté comme négative. dans le cas contraire, tu ajoute un cable de la taille de ta chute que tu traite juste apres.

ça devrais te faire un arbre en O(n!) (au lieu de O(n^n))

salut

[millie]

J'ai pas trop réflechi au problème, mais quand je vois ça, je pensais tout de suite à : programme linéaire.

Comme tu n'es pas très bon en maths, il existe des outils qui permettent de résoudre des programmes linéaires (j'ai en tête : lpsolve). La syntaxe n'est pas très difficile, et ça te fournit directement le résultat.

Les implémentations de ce genre de programme sont performantes et t'éviteront (normalement) d'avoir des complexité catastrophique en n^n.