Bonjour, 
J'ai rassemblé les données de ton problème, pour la clarté de l'énoncé.
Envoyé par
Fixette2000
... On me donne un mur d'une certaine largeur; je dois y installer une série de cadres photos en utilisant un stock de 4 modèles de cadres différents (Par exemple cadre A 30cm de large, cadre B 40cm de large, cadre C 50cm de large, cadre D 70cm de large).
Je dois respecter un écart de 8 cm entre chaque cadre et au minimum 6 cm d'espace entre les 2 cadres d'extrémité et le bord du mur, je peux utiliser plusieurs fois le même modèle de cadre ...
Envoyé par
Fixette2000
... je n'aurais pas de murs de plus de 35 m à priori ...
Envoyé par
Fixette2000
... J'ai un stock de cadres photos de 4 largeurs différentes et je peux en racheter si besoin;
(ICI considérant que j'ai un stock illimité de cadres)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
Cadre A de largeur 30cm (vA) au nombre illimité (n 8) ou limité (nA)*
Cadre B de largeur 40cm (vB) au nombre illimité (n 8) ou limité (nB)*
Cadre C de largeur 50cm (vC) au nombre illimité (n 8) ou limité (nC)*
Cadre D de largeur 70cm (vD) au nombre illimité (n 8) ou limité (nD)*
J'ai un mur (m) de largeur connue (vm)
Je cherche à obtenir la meilleure combinaison (et donc la quantité de chaque type de cadres nécessaire) pour remplir au maximum le mur
sachant que:
-on peut choisir plusieurs fois ou aucune fois chaque cadre.
-vm est supérieur ou égale à 1 vA
-vA, vB, vC, vD sont tous supérieur à 0
selon plusieurs cas:
Cas 1: J'ai un stock illimité de cadres et je cherche (dans l'ordre des opérations) la solution qui remplisse le plus le mur, puis qui utilise le moins de cadres.
(*Cas 2: j'ai un stock limité de chaque type de cadres (par exemple nA=12 nB=12 nC=12 nD=12) et je cherche (dans l'ordre des opérations) la solution qui remplisse le plus le mur, puis qui utilise le moins de cadres. )
Cas3: je veux utiliser en priorité les plus grands cadres (en dernier lieu les plus petits cadres, par exemple A+A+A+A+C+C+C+BB+A) quitte à accepter une solution de 10% moins optimale que la solution du cas 1 (ou*cas2)
=(algorithme glouton/division euclydienne)
Cas 4: je veux un calepinage de composition parfaitement symétrique (par exemple A + B + C + B +A
ou encore A+B+C+D+D+C+B+A)
Question programmation, je souhaiterais combiner ces 3 ou 4 algorithmes pour voir s'afficher dans l'ordre:
-La combinaison la plus optimale, c'est à dire la plus approchante de la valeur (vm) du mur
-La combinaison la plus optimale, à condition qu'elle utilise le maximum de grands cadres
-La combinaison la plus optimale, à condition qu'elle permette une symétrie dans son agencement, en utilisant si possible les plus grands cadres en priorité |
Ne pourrais-tu pas envisager d'introduire
a) la largeur effective du mur: Lm = Vm - 4 ;
b) les largeurs effectives de chaque cadre; La = Va + 2*(8/2) = Va + 8 ; Lb = Vb + 8 ... etc ?
Tu retrouverais ainsi les écarts minimaux à respecter
- entre deux cadres consécutifs: 8/2 + 8/2 = 8 cm ,
- entre le bord du mur et le premier (ou dernier) cadre: 8/2 + 4/2 = 6 cm ,
ainsi que les valeurs maximales des nombres de chaque type de cadres:
NaMax = Trunc(Lm/La) , NbMax = Trunc(Lm/Lb) , NcMax = Trunc(Lm/Lc) , NdMax = Trunc(Lm/Ld) .
Il te suffirait, dans le cas éventuel d'un stock limité, d'ajouter les corrections conditionnelles:
NaMax = Min(NaMax, NaLim) = Min(NaMax, 12) , NbMax = Min(NbBax, NbLim) ... etc
ce qui d'ailleurs limiterait salutairement le nombre total de combinaisons à
NaLim*NLlim*NcLim*NdLim = 124 = 20736
.
La recherche de la combinaison optimale pourrait alors relever
a) soit d'une énumération complète à l'aide de 4 boucles imbriquées, par un algorithme du type:
1
2
3
4
5
6
7
8
9
|
FOR Ia:= 1 TO NaMax DO
FOR Ib:= 1 TO NbMax DO
FOR Ic:= 1 TO NcMax DO
FOR Id:= 1 TO NdMax DO
BEGIN
Ltot:= Ia * La; Inc(Ltot, Ib * Lb); Inc(Ltot, Ic * Lc); Inc(Ltot, Id * Ld);
IF (Ltot<=Lm) THEN <Examen des critères>
END |
ou si le mur apparaît trop large et les combinaisons trop nombreuses, d'un tirage aléatoire:
1
2
3
4
5
6
7
|
REPEAT
Na:= 1 + Random(NaMax); Nb:= 1 + Random(NbMax);
Nc:= 1 + Random(NcMax); Nd:= 1 + Random(NdMax);
Ltot:= Ia * La; Inc(Ltot, Ib * Lb); Inc(Ltot, Ic * Lc); Inc(Ltot, Id * Ld);
IF (Ltot<=Lm) THEN <Examen des critères>
UNTIL <Critère d'arrêt>; |
Le bloc d'instructions <Examen des critères> consisterait à vérifier les conditions données, selon l'ordre de préséance indiqué.
Remarque: il est possible d'abréger l'énumération par une évaluation plus progressive des limites supérieures (NbLim, NcLim), et par la suppression de la dernière boucle: on peut en effet calculer directement (Nd) en fonction des 3 autres termes.
Discussion :
Répondre avec citation
Partager