Discussion :

[bruno.rotrou]

Bonjour,
J'ai le problème suivant :

j'ai une hauteur connu que je dois remplir et optimiser pour qu'elle soit entièrement rempli. Pour cela je dispose de 4 types d'éléments A,B,C chacun de ces éléments est un tableau(List) d'objets qui ont une hauteur, ces tableaux sont triés de manière décroissante, chaque hauteur de n'importe quel type est un multiple de 5 ex :

A(25,20,15,10) B(100,85,70,25,15) C(90,75,60,45,30)

il y a qq contraintes :
on doit toujours essayer de placer un et un seul A. Bien que ce type soit optionnel on essaie au max d'en placer 1
L'elément B est obligatoire (un et un seul) si pas d’élément B possible la combinaison ne peut être résolue , on arrete là
L'élément C est optionnel mais il peut y avoir pour finir la combinaison plusieurs éléments C.
On privilégie d'abord les grandes hauteurs
J'ai une tolérance de -5cm mais je dois toujours essayer de tomber juste

Je dois donc construire l'objet le plus optimiser possible (avoir rempli toute la hauteur connue )

quelque exemple attendu
pour une hauteur de :
60 -> A=15,B=15,C=30
95 -> A=25,B=70
220 -> A=15,B=85,C=2*60

Voilà ce que je fait mais je ne suis pas certain que cela soit très optimisé, c'est pour cela que j'ai besion de vos lumières ;-) (pour info c'est ecrit en PHP)
-Je choisie arbitrairement la A la plus grande A=25
- J'itere sur B
- pour chaque elément de B je verifie si A+B < H (si > j'essais sans le A si toujours > impossible décomposition )
******** si oui j'essaie de placer un C de manière a ce que A+B+C(n fois) <= h si le reste est divisible par 5 je considère que je peux mieux faire
*********** je contrains donc la prochaine boucle a essayer avec le A juste au dessous de 25, je passe a 20 et je recommence avec touts les B ainsi de suite jusqu'a épuisement de tous les A , j'essais une nouvelle boucle sans les A
si le resultat est inferieur a H et qu'il ne peut pas tomber juste je regarde ma tolérance si je suis dans les clous (5cm) c'est Ok si je suis au dessus : impossible décomposition

Y aurait'il une approche plus mathématique a ce problème ? je ne suis pas un grand matheux mais avec des efforts j'arrives a suivre.
Merci a celles et a ceux qui prendront un peu de leur temps.

[Flodelarab]

Bonjour

Constat préliminaire : dans le groupe C les valeurs 60 et 90 ne servent à rien puisqu'elles sont des multiples de 30 qui est dans le groupe C également.
On remarque d'ailleurs que le groupe C peut fournir tous les multiples de 15 sauf 1.
0 = 0*15
30 = 2*15
45 = 3*15
60 = 30+30 = 2*2*15 = 4*15
75 = 5*15
90 = 30 + 30 +30 = 3*2*15=6*15
105 = 75+30 = 7*15
etc...
groupe C donne 15*k avec k appartenant à ℕ\{1}.

De plus, comme A et B ont un élément obligatoire, alors tu remplis déjà 25 (=15+10).
Et on ne considère plus (25;20;15;10) mais (+15;+10;+5;+0); ni (100;85;70;25;15) mais (+85;+70;+55;+10;+0)
On remarque alors que A peut servir de réglage fin jusqu'à 15 et que C peut finir le boulot.
B devient alors (+5*15+10;+4*15+10;+3*15+10;+0*15+0)

Exemple 1 : 60
60 - 25 = 35
35 = 15 * 2 + 5
Le 5 sera réglé par A, et 2*15 par C.
Résultat: 15 ; 15; 30

Exemple 2 : 95
95 - 25 = 70
70 = 4*15+10
Le correctif de 10 pourrait être fait par A et le reste par C. Mais on tombe juste sur une valeur de B. Donc il y a le choix.
Résultat: 20+15+60 ou 10+85

Exemple 3: 220
220 - 25 = 195
195 = 15*13+0
Résultat : 10+15+90+75+30 ou 15+100+75+30 par exemple.

La clé est de diviser par 15.

[bruno.rotrou]

Merci, j'étudie cela et je reviens

[tbc92]

Le raisonnement de Flodelarab est bon, mais il s'appuie sur l'exemple , avec C(90,75,60,45,30).
J'imagine que c'est un exemple. Et demain, on peut avoir C(80,75,60,45,30) : j'ai changé uniquement la 1ère valeur de C, et le travail de Flodelarab ne sert plus à rien.

Ici, tu as peu de données. Recenser toutes les combinaisons, ça va aller très vite.
Dans B, tu as l'obligation de prendre un élément et un seul.
Dans A, tu as le choix entre un élément ou 0. Pour simplifier le traitement, je vais ajouter un élément dans A, un élément de hauteur 0 , donc A=(25,20,15,10,0).
L'élément 0 est en dernier, donc on analysera les combinaisons avec A=0 en tout dernier recours.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
h = hauteur totale (h=220 par exemple)
pour ecart = 0 à 5 pas 5   // On rechercher d'abord une solution pour écart=0, puis si on ne trouve pas, on cherche pour écart=5
Pour tout ia de A              // Je parcours d'abord A, puis B, comme ça, la solution A=0 sera explorée en tout dernier recours.
  Pour tout ib de B
    h0 = h - ia-ib
    pour tout ic de C
        si mod ( h0, ic) = ecart alors    
            n = (h0-ecart) / ic 
            print ( " solution trouvée, ia="+ ia + " ib= "+ ib + " ic= " + ic + " répété " + n + " fois" + " ecart= " + ecart)  
            return
        fin
   fin
fin
print (" pas de solution")

Ce code va donner une solution si il y en a une, mais peut-être que ce ne sera pas celle que tu préfères.
Par exemple , avec A(80,75,50,35) B(50,45,40,35) et C(15,10) et Hauteur=200, on va trouver A=80,B=50,C=7*10), alors que tu aurais peut être préféré (A=80, B=45, C=5*15) ou encore (A=75,B=50,C=5*15)

Ici, je privilégie A le plus grand possible, puis B le plus grand possible, puis on prend C pour compléter, et tant pis si on prend plein d'exemplaires de C, avec C a une hauteur très petite.

Je m'arrête dès que je trouve une solution. Tu peux modifier le programme pour lister toutes les solutions, et dans un 2nd temps, choisir la solution qui te plait le mieux.

[bruno.rotrou]

Merci a vous deux, cela m'éclaire bien, je viens vers vous des que j'ai pu décortiquer et essayer tout cela
Merci encore