Discussion :

[vms09]

bonjour
j'ai un probleme fort simple et je ne sais pas comment le prendre.

j'ai une liste de nombres entiers positifs mettons de 1 à 5000, il n'y a pas de limite sur la quantité mais disons 300 maximum qui représentent des longueurs de pieces de bois
j'ai une longueur fixe que je vais appeler longueur d'une barre de bois.

Allez vous avez compris, le but du jeu est d'optimiser le nombre de barres de bois que je vais acheter chez le marchant pour pouvoir y loger toutes mes longueurs de pieces de bois.

Je ne sais pas comment prendre l'algorithme, si vous avez des idées.

après, sans vouloir abuser, il faudrait que ce soit codable sous excell facilement.

merci de votre aide

[SpiceGuid]

Ce problème a déjà été abordé plusieurs fois sur ce même forum (utilise la fonction recherche).

Il s'agit d'un problème d'optimisation de ressource connu sous le nom de problème du sac-à-dos ou knapsack problem.

[Invité]

Dans la littérature anglaise, ce problème est connu sous le nom de "cutting stock" (je ne crois pas que ce soit le même que le sac à dos, dans le problème du sac à dos, il n'y a qu'un sac, ici il y a plusieurs planches).

http://en.wikipedia.org/wiki/Cutting_stock_problem

C'est à priori un problème difficile (problème linéaire en entiers).

Si tu n'as pas trop de pièces différentes, ca doit pouvoir se faire à la main (la combinatoire n'est pas trop compliquée).

Sinon, tu peux facilement bâtir des algorithmes qui donneront une 'assez bonne' solution.

Mon approche serait (sous excel) de trier les pièces par ordre décroissant de taille, et de partir des plus grandes. A chaque étape, on élimine une pièce et on raccourcit une barre (ce qui fait que toutes les barres n'ont pas la même taille). On choisit pour cela la plus petite barre disponible (je ne suis pas certain que ce soit la meilleure solution, si on doit améliorer la méthode, c'est là qu'il faut chercher), qu'on recoupe, et ainsi de suite... De cette façon, on essaye de gâcher le moins possible.

L'approche n'est pas optimale. Peut être faudrait il chercher à utiliser au mieux les petites chutes, dès qu'elles atteignent une certaine taille.

La façon d'aborder le problème va beaucoup dépendre de la structure de tes pieces...

Francois

[pseudocode]

Dans la littérature anglaise, ce problème est connu sous le nom de "cutting stock" (je ne crois pas que ce soit le même que le sac à dos, dans le problème du sac à dos, il n'y a qu'un sac, ici il y a plusieurs planches).

Tout a fait. C'est plus un problème de "packing" que de sac à dos. Comme l'a dit SpiceGuid on en a déjà parlé sur le forum, par exemple ici.