[VBA] Algo sac a dos 1D Fermé

Question

Bonjour,
étant débutant en programmation, je fais actuellement un programme pour le problème du sac à dos 1D, également connu sous le nom de Bin Packing 1D, avec lequel j'ai un problème ... 

Ce programme consiste a trier des valeurs (de n'importe quel type) de façon à avoir un gain de place ou de matière sur le principe du Bin Packing 1D.

Exemple:
Je dispose de données informatiques de différentes tailles que je veux mettre sur CD, j'essai donc d'optimiser la place afin d'utiliser le moins de CD possible:

Données de 500mo, 400mo , 300mo et 100mo.
Place sur CD 700mo.

Il est donc logique de placer 400 et 300 ensemble pour remplir un CD et 500 et 100 ensemble pour le second.
Dans ce cas j'utilise 2 cd, pour les autres solutions au moins 3.


Voir également https://fr.wikipedia.org/wiki/Probl%C3%A8me_de_bin_packing
et https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_sac_%C3%A0_dos

Dans mon cas, je créé ce programme pour optimiser la découpe de barre (comme en menuiserie).

J'ai des barres standard de 2500mm et j'aimerai les découper en barres de différentes longueurs (exemple 1000, 1345, 537 ,886... dans des quantités plus importantes (>1000)) en utilisant le moins de barres standard possible.

J'utilise donc la méthode Deacrising First Fit (qui consiste a trier les longueurs dans l'ordre décroissant puis de les ranger au fur a mesure dans la 1ere barre ou il y a de la place).

En reprenant l'exemple du CD.

Dans l'ordre décroissant j'ai 500,400,300,100

CD1 je place 500.
400 ne rentre plus de CD1 (400+500>700), je créé donc un CD2 pour le placer dedans.
300 ne rentre pas dans CD1, 300 rentre dans CD2. On rajoute 300 au CD2.
100 rentre dans CD1, on le rajoute au CD1.

J'utilise également la méthode du Deacrising Best Fit qui est plus précise, mais je n'ai pas de réèl intérêt à prendre ce dernier car mon programme est utilisé pour des grandes séries de barres (plus de 1000 fois la même valeur).
Je trouve donc le même résultat qu'en Next Fit mais en un temps beaucoup plus important.

Mon problème 
Mon problème est que je ne trouve pas , dans de rare cas, une solution suffisament proche de l'optimale.

Exemple: j'ai des barres de 2500, j'aimerai 10 barres de 1000 et 20 de 700.

L'optimale est d'avoir 10 barres de 2500 qu'on découpe en 1000+700+700 = 2400.

Mais en Decreasing First Fit ou Next Fit je me retrouve avec 5 barres de 1000+1000=2000 et 6 barres de 700+700+700 = 2100 et 1 barre de 700+700=1400.

Soit un surplus de 20% (12 barres au lieu de 10).

Je sais que ma méthode est heuristique (permet de trouver rapidement un résultat approché de l'optimal), mais je sais également qu'il est possible d'avoir un tri plus approché dans le cas ci dessus, seulement je ne sais pas comment faire.

Pouvez vous m'aider?

Merci

yg_be · Answer

Tu nous décrit le First Fit, et tu nous explique qu'il ne donne pas de bons résultats.  De toutes évidence il ne convient pas dans ton cas.
Il ne s'agit pas vraiment d'un problème de programmation, il s'agit de choisir le bon algorithme.
Comment fais-tu pour arriver au résultat sans programmer ?  Tu peux t'en inspirer.
Quelques idées :
1) Au départ, tu mets tes barres dans une liste.  C'est à ce moment-là que tout se passe.  Au lieu de les trier par ordre de taille, tu pourrais aussi bien prendre le plus grand restant, puis le plus petit restant, et ainsi de suite.  Ou les mettre dans un ordre aléatoire.  Suggestion, essaie de multiples fois par ordre aléatoire, et garde le meilleur.
2) Comme tu sais que tu as un grand nombre de barres identiques, tu travailles sur un plus petit nombre, et tu extrapoles.
3) Tu connais le nombre minimum de barres dont tu as besoin.  Tu répartis tes pièces dans ces barres, en essayant de laisser le plus grand espace libre  possible dans chaque barre (sauf si tu peux remplir completement une barre).  Donc, au lieu de tout mettre dans les premières barres, tu mets dans la barre où il reste le plus de place (ou bien où la place qui reste correspond à ta pièce).  Quand tu as besoin de barres supplémentaires, tu en crées.

yg_be · Answer

La seule "bonne" méthode, selon moi, c'est l'algorithme suivant :

1) calculer, dans l'ensemble des découpes encore à faire, toutes les sommes possibles qui sont inférieures à une barre (dans ton cas, au départ : 1000, 1000+1000, 1000+700, 1000+700+700, 700, 700+700, 700+700+700)
2) tu prends la plus grande somme (dans ton cas, 1000+700+700)
3) tu supprimes les découpes sélectionnées (1000,700,700) de la liste des decoupes encore à faire
4) tu recommences en 1

cela me semble un bon exercice de programmation, non ?

[VBA] Algo sac a dos 1D

2 réponses

Discussions similaires