[VBA] Algo sac a dos 1D
Fermé
sfritz
Messages postés
41
Date d'inscription
jeudi 9 octobre 2008
Statut
Membre
Dernière intervention
1 janvier 2014
-
23 juin 2009 à 11:24
yg_be Messages postés 23230 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 27 septembre 2024 - 15 août 2009 à 14:53
yg_be Messages postés 23230 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 27 septembre 2024 - 15 août 2009 à 14:53
2 réponses
yg_be
Messages postés
23230
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
27 septembre 2024
Ambassadeur
1 538
24 juin 2009 à 08:26
24 juin 2009 à 08:26
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.
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
Messages postés
23230
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
27 septembre 2024
Ambassadeur
1 538
24 juin 2009 à 12:14
24 juin 2009 à 12:14
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 ?
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 ?
bonjour
moi aussi je m'interesse a cet algo pour des besoins professionnels
en effet la derniere description semble etre LA maniere de procéder.
Maintenant quand on a une liste de base de mettons 300 découpes, calculer toutes les sommes possibles qui sont inférieures a la longueur de la barre, ca parait chaud non en temps de calcul et en stockage mémoire?
mais s'il y a des solutions que je ne connais pas, je suis preneur
Rémy
moi aussi je m'interesse a cet algo pour des besoins professionnels
en effet la derniere description semble etre LA maniere de procéder.
Maintenant quand on a une liste de base de mettons 300 découpes, calculer toutes les sommes possibles qui sont inférieures a la longueur de la barre, ca parait chaud non en temps de calcul et en stockage mémoire?
mais s'il y a des solutions que je ne connais pas, je suis preneur
Rémy
yg_be
Messages postés
23230
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
27 septembre 2024
1 538
>
vms09
15 août 2009 à 14:53
15 août 2009 à 14:53
En fait, il ne faut pas calculer toutes les sommes possibles, il faut rechercher la combinaison qui donne la plus grande somme possible avec le nombre minimum d'élements. Cela me semble facile pour un ordinateur, à condition de bien programmer cela.