Discussion :

[Fixette2000]

Bonjour,

je suis tout à fais nul en math, et encore plus en algorithme, mais j'ai un gros besoin.
Je pense que c'est un algorithme d'optimisation avec contraintes qu'il me faut.
Etant ignare de ce langage, je cherche un coup de pouce pour me dire comment je dois procéder, dans quel ordre je dois faire les choses, ou au mieux, s'il existe un algorithme tout fait.

Je vous explique mon problème:

Je cherche une formule me permettant d'afficher plusieurs solutions selon plusieurs critères en fonction d'une variable principale (largeur de mur) et des variables implicites (nombre de cadres).

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 8cm entre chaque cadre et au minimum 6cm 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.

1-je voudrais calculer automatiquement la meilleur combinaison pour remplir au maximum la largeur du mur selon les critères cités au dessus.

2-je voudrais également trouver la meilleur combinaison pour remplir au maximum le mur, mais en utilisant le minimum de cadres, donc en priorisant les plus grands cadres, tout en recouvrant au maximum le mur, selon les critères cités au dessus. (exemple cadre D

3-je voudrais aussi calculer la meilleure combinaison qui remplisse au maximum le mur, toujours selon les critères cités au dessus, mais cette fois en ayant une symétrie parfaite dans le calepinage (exemple cadre A, cadre B, cadre C, cadre B, cadre A).

En fait, j'aimerais pouvoir calculer automatiquement ces 3 solutions, et voir aussi toutes les autres solutions, classées de la plus approchante à la moins approchante de la perfection.

Les variables sont donc la dimension du mur et le nombre de cadres utilisés (donc nombre d'écarts de 8cm)

Comment pensez-vous que je doive faire?

Chaque tentative d'ajouter un cadre dans la combinaison implique un nombre d'écarts de 8cm différents, l'algorithme doit donc calculer automatiquement la somme totale des cadres et écarts au fur et à mesure.

ça ne me semble pas impossible mais je devine qu'il y a un problème de recalcule constant.
Pensez-vous qu'il faille avant tout faire un tableau de données avec toutes les solutions possibles (fastidieux) pour que l'algorithme puise dans ces données pour faire le calcul?

Je vous remercie d'avance pour tout conseil, suggestion qui pourrait me faire avancer.

[CliffeCSTL]

Je te propose de résoudre avec la programmation linéaire :

1 :

Données :

Variable de décisions :






Programme linéaire :

Contraintes :

2. Tu dois pondérer les deux critères d'optimisations.
3. Il suffit de résoudre le pb en remplissant la moitié du mur, avec la possibilité de mettre au maximum une fois la moitié d'un cadre.

[Fixette2000]

Bonjour,

merci pour cette réponse.

Hier sur un autre forum, 2 contributeurs m'ont plutôt guidés vers du code type VBA;
Ici vous me proposez une mise équation que j'ai beaucoup plus de mal à interpréter mais qui me semble plus didactique.

Je ne saurais pour l'instant mettre en parallèle les 2 langages mais je vais me faire mettre dans la peau de Champollion face à la pièce de rosette

En étudiant les problèmes de sac à dos, j'ai l'impression qu'il faut utiliser 3 méthodes différentes pour mes 3 objectifs:

-remplir le mur au maximum (sac à dos multi-objectif?/Procédure de séparation et d'évaluation?)

-utiliser le minimum d'éléments pour remplir au maximum le mur (Algorithme glouton? procédé d'exploration systématique?)

-obtenir une symétrie parfaite qui rempli au maximum le mur (comme vous dites, travailler sur la moitié de la dimension totale voulue))


Bon je mélange un peu tout, mais je sens que le choix de la méthode selon les objectifs est crucial pour ne passer à cotés de solutions plus efficaces que je pourrais trouver de façon empirique…

Je vis étudier tout ça au rythme de ma compréhension, vous avez peut-être exprimé tout cela mais je suis comme un aveugle à qui on essaye d'expliquer une couleur pas facile

Merci en tout cas

[CliffeCSTL]

La méthode pour résoudre ton problème va dépendre de :
1. la taille de celui-ci
2. le temps maximal autorisé pour avoir un résultat

Ma méthode ne te donnera que la solution exacte et est intéressante pour des instances de taille moyenne.



Une autre solution consiste à tester toutes les combinaisons possibles, à afficher celles qui sont réalisables, et à retourner la meilleure trouvée.
Avec un algo de principe ça donne ça :

Code :

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

1
2
3
4
5
6
Pour toutes les combinaisons possibles parmi l'ensemble des cadres 
    Si la combinaison courante est réalisable alors
        Afficher la solution
        Si la combinaison courante est une meilleure solution  alors
            mémoriser la combinaison comme meilleure solution

Cette manière de faire est simple et rapide à coder, mais pas du tout adapter sur des grosses instances (Largeur très grande avec des milliers ou millions de cadres)



Après, pour les grosses instances, tu as aussi des méthodes exactes ou approchées mais plus compliquées à mettre en œuvre, à voir tes besoins...

[Fixette2000]

Ok, merci Cliffe CSTL, c'est très clair.

...Effectivement il est possible que j'ai des murs très grands, donc beaucoup plus de possibilités à tester.

Je me dis maintenant qu'il me faudrait peut-être 2 algorithme à utiliser selon la taille du mur.

J'y vois plus clair maintenant...au travers la brume, mais je devine mon objectif

Merci encore

[tbc92]

La question des performances et des temps de calcul : Ce n'est pas un problème.

Dans ton exemple, tu parles de 4 ou 5 cadres sur un mur. Dans la vraie vie, tu auras 10, 20, éventuellement 50 cadres au grand maximum ! Ca reste des petits nombres. Comme disait CliffeCTL, tu vas avoir des problèmes de performance si tu dois placer quelques milliers ou quelques millions de cadre sur un seul et même mur ... configuration purement théorique donc.
Et si par hasard, le calcul que tu dois lancer doit prendre 3 minutes pour trouver la meilleure réponse à chacune des questions, je pense que ça ne te dérange pas vraiment.

[Fixette2000]

ok, et bien tant mieux.
J'avais une crainte la-dessus. Effectivement je n'aurais pas de murs de plus de 35m à priori

merci

[valentin03]

Tant que tu n'aura pas défini(s) ton (ou tes) cahier(s) des charges et qu'ils seront fixés et définitifs tu ne pourra rien faire. Pour qu'il y ait une solution il faut qu'il y ait un problème.

[Fixette2000]

Merci Valentin.

Veux-tu dire ceci?: Tant que je n'ai pas défini mon cahier des charges (suite d'opération recherchées?), que je ne l'ai pas fixé définitivement (en rentrant des valeurs, une équation?), je ne pourrais rien faire.
Connaissant la valeurs et le nombre de cadres disponibles, connaissant la valeur du mur, puis-je programmer à partir de cela?

D'après mes recherches, je suis dans un problème d'optimisation combinatoire (du type SAC A DOS en variables entières /c.a.d. avec possiblité de répétition) que je dois résoudre par programmation dynamique, notamment avec une procédure par séparation et évaluation (PSE).
(Ou bien problème de type RENDU DE MONNAIES avec une monnaie non canonique?)

Mon besoin (objectif) c'est de savoir combien de chaque cadre je dois utiliser pour remplir au maximum le mur en respectant les contraintes d'écart entre cadres, et au mieux les écarts entre cadre et fin de mur.

A priori un algorithme de type glouton ne me donnera pas forcément la solution otpimale.


Je découvre algorithmes et programmation depuis 1 semaine...pas facile de s'y retrouver.

[Fixette2000]

CliffeCSTL :

je retourne la question depuis ce temps, et je recentre.

que penses-tu de cet algorithme?

[tbc92]

Voici un programme qui fait le job. J'ai testé un peu, ça me semble correct.
- Je considère qu'il y a 4 tailles de tableaux au maximum, On peut adapter facilement pour 5 , voire 6 tailles de tableaux. Si on voulait plus de souplesse sur ce critère, il faudrait organiser le programmme très différemment.
- Je ne traite pas le 1er cas que tu proposes. Ce 1er cas fait complètement doublon avec le 2ème cas.
- Pour le 3ème cas (disposition symétrique), je pars de cette propriété : les tableaux pourront être disposés de faàons symétrique si on a un nombre pair pour chaque taille, ou au maximum une taille de tableau qui est en nombre impair.
Ce qui se traduit par cette instruction :

Code :

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

SI modulo(i1,2) +modulo(i2,2)+modulo(i3,2)+modulo(i4,2) <= 1 ALORS

Le code complet :

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
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
tb_larg est un tableau de 4 entiers
lgtot est un entier
lg_intercalaire est un entier = 8
tab_Nbtableaux est un tableau de 4 entiers
tab_Best_scenario est un tableau de 4 entiers 
nScore_best_scenario est un entier 
ntableaux_best_scenario est un entier 
 
 
tab_Best_scenario_sym est un tableau de 4 entiers 
nScore_best_scenario_sym  est un entier 
score est un entier 
 
 
tab_Nmax est un tableau de 4 entiers
 
i1,i2,i3,i4 est un entier 
 
lgtot = 1100    // 11 mètres =1100 cm.
tb_larg = [90, 75, 60, 50 ]    // Je mets les largeurs des tableaux en ordre décroissant, pour que le programme soit plus rapide.
 
tab_Nmax[1] = (lgtot - lg_intercalaire) / (tb_larg[1] + lg_intercalaire)  // Si je mets uniquement des tableaux de type 1, je peux en mettre au max combien ?
POUR i1 = 0 _A_ tab_Nmax[1]
	// je fais une hypothèse ; je mets i1 tableau de type 1.
	tab_Nmax[2] = (lgtot - lg_intercalaire - i1 * (tb_larg[1] + lg_intercalaire) ) / (tb_larg[2] + lg_intercalaire)
	// Du coup, avec i1 tableaux de type 1, je peux mettre au max  tab_Nmax[2]  de type 2
	POUR i2 = 0 _A_ tab_Nmax[2]
		// je fais une hypothèse ; je mets i1 tableau de type 1 et i2 tableaux de type 2.
		tab_Nmax[3] = (lgtot - lg_intercalaire - i1 * (tb_larg[1] + lg_intercalaire) - i2 * (tb_larg[2] + lg_intercalaire)  ) / (tb_larg[3] + lg_intercalaire)
		// Du coup, avec i1 tableaux de type 1,et i2 tableaux de type 2,  je peux mettre au max  tab_Nmax[3]  de type 3
		POUR i3 = 0 _A_ tab_Nmax[3]
			tab_Nmax[4] = (lgtot - lg_intercalaire - i1 * (tb_larg[1] + lg_intercalaire) - i2 * (tb_larg[2] + lg_intercalaire) - i3 * (tb_larg[3] + lg_intercalaire)  ) / (tb_larg[4] + lg_intercalaire)
			POUR i4 = 	tab_Nmax[4]-1 A tab_Nmax[4]
				// La configuration i1, i2, i3, i4 convient , je peux placer  (i1, i2, i3, i4 ) tableaux sur mon mur.		
				// Cette configuration est-elle mieux que la meilleure configuration déjà rencontrée.
				score = i1* tb_larg[1] + i2* tb_larg[2] + i3* tb_larg[3] + i4* tb_larg[4] 					
				SI score > nScore_best_scenario _OU_ ( score = nScore_best_scenario _ET_ i1+i2+i3+i4 < ntableaux_best_scenario ) ALORS 
					nScore_best_scenario = score 
                                        ntableaux_best_scenario = i1+i2+i3+i4
					tab_Best_scenario[1] = i1
					tab_Best_scenario[2] = i2
					tab_Best_scenario[3] = i3
					tab_Best_scenario[4] = i4							
				FIN
				// Recherche du meilleur résultat, avec une répartition symétrique 
				SI modulo(i1,2) +modulo(i2,2)+modulo(i3,2)+modulo(i4,2) <= 1 ALORS
					score = i1* tb_larg[1] + i2* tb_larg[2] + i3* tb_larg[3] + i4* tb_larg[4] 					
					SI score > nScore_best_scenario_sym ALORS 
						nScore_best_scenario_sym = score 
						tab_Best_scenario_sym[1] = i1
						tab_Best_scenario_sym[2] = i2
						tab_Best_scenario_sym[3] = i3
						tab_Best_scenario_sym[4] = i4							
					FIN
				FIN
			FIN
		FIN
	FIN
FIN
 
Info ( " Meilleur scénario remplissage ",tab_Best_scenario[1]  , tab_Best_scenario[2] , tab_Best_scenario[3] , tab_Best_scenario[4]  )
Info ( " Meilleur scénario remplissage + symétrie ",tab_Best_scenario_sym[1]  , tab_Best_scenario_sym [2] , tab_Best_scenario_sym[3] , tab_Best_scenario_sym[4]  )

Une fois qu'on connait le nombre de tableaux pour chaque dimension, la disposition elle-même peut être quelconque.

Le programme affiche les 2 réponses en quelques centièmes de seconde.

[valentin03]

Merci Valentin.

Veux-tu dire ceci?: Tant que je n'ai pas défini mon cahier des charges (suite d'opération recherchées?), que je ne l'ai pas fixé définitivement (en rentrant des valeurs, une équation?), je ne pourrais rien faire.
Connaissant la valeurs et le nombre de cadres disponibles, connaissant la valeur du mur, puis-je programmer à partir de cela?

D'après mes recherches, je suis dans un problème d'optimisation combinatoire (du type SAC A DOS en variables entières /c.a.d. avec possiblité de répétition) que je dois résoudre par programmation dynamique, notamment avec une procédure par séparation et évaluation (PSE).
(Ou bien problème de type RENDU DE MONNAIES avec une monnaie non canonique?)

Mon besoin (objectif) c'est de savoir combien de chaque cadre je dois utiliser pour remplir au maximum le mur en respectant les contraintes d'écart entre cadres, et au mieux les écarts entre cadre et fin de mur.

A priori un algorithme de type glouton ne me donnera pas forcément la solution otpimale.


Je découvre algorithmes et programmation depuis 1 semaine...pas facile de s'y retrouver.

Dans ton message initial tu veux trois options, or, une option => un algo; je doute qu'avec un seul algo tu ai les trois options, traite donc les problèmes en options distinctes, tu verra après si tu peux les regrouper.

[Fixette2000]

Merci pour ta participation tbc92

[QUOTE=tbc92;11187706]
- Je ne traite pas le 1er cas que tu proposes. Ce 1er cas fait complètement doublon avec le 2ème cas. QUOTE]

Alors justement, il semble que non.
Par exemple il est possible que 10 cadres de petites tailles remplissent mieux l'espace que 5 cadres de grande tailles.
C'est l'inconvénient de l'algorithme de type glouton, qui ne donne pas obligatoirement la solution optimale.
Dans le système de rendu de monnaie par exemple, on peut partir de la plus grande pièce, pas dans mon cas.

Pour le reste, je vais me pencher dessus et traduire comme je peux
Merci

[Fixette2000]

Dans ton message initial tu veux trois options, or, une option => un algo; je doute qu'avec un seul algo tu ai les trois options, traite donc les problèmes en options distinctes, tu verra après si tu peux les regrouper.

Effectivement. Il faudrait une combinaison d'algorithmes.

J'ai revu mon énoncé dans ce sens:


J'ai un stock de cadres photos de 4 largeurs différentes*:
Cadre A de largeur 30cm (vA) au nombre illimité ou limité (nA)
Cadre B de largeur 40cm (vB) au nombre illimité ou limité (nB)
Cadre C de largeur 50cm (vC) au nombre illimité ou limité (nC)
Cadre D de largeur 70cm (vD) au nombre illimité 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
Cas 2*: j'ai un stock limité de chaque type de cadres (nA=12 nB=12 nC=12 nD=12)
Cas3*: je veux utiliser un maximum des grands cadres dans la combinaison (utiliser en priorité D puis C puis B puis A / par exemple D+D+C +B+A)
Cas 4*: je veux avoir un calepinage de composition parfaitement symétrique (par exemple A + B + C + B +A)

Question programmation, je souhaiterais bien sur trouver la bonne formulation pour combiner tout ça (en langage C si possible) pour voir s'afficher les 4 solutions de la plus approchante à la moins approchante de la dimension idéale (vm)
...mais déjà résoudre chaque cas serait un exploit pour moi.

[tbc92]

J'avais interprété le premier message de la façon suivante :
- Cas n°1 : la somme des largeurs des tableaux doit être la plus grande possible.
- Cas n°2 : la somme des largeurs des tableaux doit être la plus grande possible, et si plusieurs solutions sont ex-aequo, on les départage en prenant celle qui a le moins de tableaux.

C'est pour ça que je disais que les 2 cas étaient similaires. Le départage par le nombre de tableaux ne se fait qu'en cas d'ex-aequo.

Dans ta nouvelle formulation, il y a des ambiguités. Tu mets sur un même plan 2 notions qui sont très différentes :

Cas 1*: J'ai un stock illimité de cadres
Cas 2*: j'ai un stock limité de chaque type de cadres (nA=12 nB=12 nC=12 nD=12)
Cas3*: je veux utiliser un maximum des grands cadres dans la combinaison (utiliser en priorité D puis C puis B puis A / par exemple D+D+C +B+A)
Cas 4*: je veux avoir un calepinage de composition parfaitement symétrique (par exemple A + B + C + B +A)

Les 2 lignes Cas 1 et Cas 2 décrivent les contraintes.
Alors que les lignes Cas 3 et Cas 4 définissent l'objectif.

Et encore, spécialement dans le cas 3, l'objectif est mal défini (il était mieux défini dans le premier message). Par exemple (faisons l'impasse sur les 8cm de part et d'autre de chaque tableau), avec des tableaux de 70, 50, 40, 30cm, sur un mur de 300cm, dans le cas 3, c'est quoi la solution idéale ?
Mettre 4 tableaux de 70cm, ou mettre 3 tableaux de 70cm, un de 50 et un de 40 ?
Dans la 1ère proposition, on a mis 4 tableaux de 70cm, contre seulement 3 dans la 2ème proposition, donc ça correspond mieux à ce que tu as écrit. Et pourtant, je suis à peu près sûr que tu préfères la proposition n°2.

Idem, toujours dans le cas 3, avec nos tableaux de 70 50 40 et 30cm, et un mur d'1,50mètre, tu préfères 70+50+30, ou 50+50+50 ?

Dans le code que j'ai proposé, tu auras 50+50+50 et non 7050+30. Pour inverser, il faut remplacer les symboles > par >=
Et c'est comme ça, parce que les longueurs sont en ordre décroissant dans le tableau tb_larg.

[Fixette2000]

tbc92

Tes questions sont pertinentes.
Dns un idéal parfait, supprimant les notions de bordures de 8cm etc., pour un mur de 210cm la solution est 70+70+70 et est proposée dans les 3 algorithmes

"Par exemple (faisons l'impasse sur les 8cm de part et d'autre de chaque tableau), avec des tableaux de 70, 50, 40, 30cm, sur un mur de 300cm, dans le cas 3, c'est quoi la solution idéale ?
Mettre 4 tableaux de 70cm, ou mettre 3 tableaux de 70cm, un de 50 et un de 40 ?
Dans la 1ère proposition, on a mis 4 tableaux de 70cm, contre seulement 3 dans la 2ème proposition, donc ça correspond mieux à ce que tu as écrit. Et pourtant, je suis à peu près sûr que tu préfères la proposition n°2.

Idem, toujours dans le cas 3, avec nos tableaux de 70 50 40 et 30cm, et un mur d'1,50mètre, tu préfères 70+50+30, ou 50+50+50 ?"

Effectivement c'est subtile...
Pour un mur de 300cm, l'algorithme du Cas 1 et Cas 2 devrait normalement trouver 3 tableaux de 70cm + 1 tableau de 50cm + 1 tableau de 40cm, mais c'est aussi la réponse que j'attend en Cas 3 si c'est la solution la plus approchante. Mais entre 2 solutions de même résultat, elle devra choisir celle qui comporte le plus de grands cadres (pour un même résultat, je préfère qu'il n'y ai qu'un cadre de 70cm que pas du tout de cadre de 70cm).

dans le cas 3, avec nos tableaux de 70 50 40 et 30cm, et un mur d'1,50mètre, tu préfères 70+50+30, ou 50+50+50 ?

J'attend du logarithme du Cas 3 qu'il me donne 70+50+30.
Considérant que le logarithme du Cas4 est là pour me donner 50+50+50.

Et pour répondre au mieux, je dirais que:
Dans le Cas 1 et 2 j'espère y trouver la solution la plus proche de la valeur du mur.
Dans le cas 3, j'espère y trouver la solution moins otpimale que Cas 1 et 2 mais qui utilise le maximum de grands cadres
Dans le cas 4 j'espère trouver la solution moins otpimale que les 2 premières mais proposant une symétrie pour compenser le manque de remplissage

C'est dans ces choix que je ne peux pas me faire remplacer par une machine.

[Fixette2000]

tbc92

par ailleurs, je n'arrive pas a tester ton code dans les quelques logiciels que j'ai (LARP, algobox, Dev-C+), mais ça c'est lié à mon ignorance dans le domaine...

[Fixette2000]

Suite à cette discussion, je reformule plus précisément mon problème, en vu de le programmer ou le faire programmer.

Toute bonne âme pour le vérifier, corriger, ou y répondre est la bienvenue.



Ennoncé du problème:

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)

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é

[tbc92]

Le code que j'ai posté est écrit en Windev. C'est un langage plutôt simple. Pour l'utiliser, il faut le compilateur Windev (payant), mais tu peux télécharger une version d'évaluation : ici .
Avec cette version d'évaluation, tu pourras modifier les paramètres , faire tout ce que j'ai fait ... A priori aucune restriction due au fait que c'est une version d'évaluation. Tu pourras très facilement faire un écran où tu saisis les 5 paramètres + un bouton qui lance les différents calculs. Et tu pourras aussi ajouter les contraintes (au maximum x tableau de largeur y)

Eventuellement, je peux essayer de le traduire en Python, mais je ne connais que les bases, je ne suis même pas sûr de savoir le faire.

Et je me répète : tes cas 1 et 2 sont similaires :
-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
Dans les 2 cas, la somme des largeurs des tableaux doit être la plus grande possible.
Dans le 1er cas, en cas d'ex-aequo, on choisit une solution comment ? au hasard ? tu nous laisses libre de choisir. Tu ne donnes de règle pour départager les ex-aequo que dans le cas 2.
Et comme je n'aime pas choisir au hasard (c'est compliqué à programmer), dans le 1er cas, en cas d'ex-aequo, je choisis en appliquant un certain critère, celui que tu donnes pour le cas n°2.

[Fixette2000]

Merci l'ami mais ne t'embêtes pas, je préfère déjà avoir le raisonnement, ce qui en découlera me dira comment faire la chose

Je me corrige plusieurs fois sur ce pot: Oui je comprend ton raisonnement, et je précise le mien:
(j'ai changé l'énoncé mais restons sur 3 cas différents, une solution optimale, une solution optimale priorité aux grands cadres, une solution optimale donnant une symétrie)

Comme il est possible par principe qu'une seule solution optimale existe (celle qui m'intéresse en priorité), et qu'elle n'utilise pas de grands cadres, le cas1 et cas2 sont bien indépendants, même si le cas2 peut venir suplanter le cas1.
Il est possible pour différentes raison que je préfère choisir une solution au plus proche complètement anarchique, j'aimerais donc voir cette solution proposée si elle diffère de la solution au Cas2

l'ordre des opérations devrait être ainsi:

Je rajoute une inconnue=LE RESULTAT=Solution choisie pour son rapprochement de la valeur du mur, puis pour son utilisation maximale de grands cadres, puis pour la symétrie potentielle qu'elle permet, tout ça par comparaison des solutions Cas1, Cas2 et Cas 3:

Cas 1:Chercher la combinaison la plus proche de la valeur du mur en piochant au hasard dans les cadres=comparer toutes les solutions et sélectionner la plus proche de vm + afficher le détail de la combinaison
Cas 2:Chercher la combinaison la plus proche de la valeur du mur en piochant en priorité dans les grands cadres=comparer toutes les solutions et sélectionner la plus proche de vm + afficher le détail de la combinaison (algorithme glouton)
Cas 3: Chercher la combinaison la plus proche de la valeur du mur qui permet une symétrie=comparer toutes les solutions et sélectionner la plus proche de vm + afficher le détail de la combinaison
ENSUITE
Comparer les 3 solutions + afficher la Solution choisie=
Si Cas2<Cas1, afficher Cas1 comme Solution choisie
Si cas 2=Cas1, afficher en priorité Cas2 comme Solution choisie
Si cas 3=Cas1, afficher en priorité Cas3 comme Solution choisie
Si cas 3 utilise autant de grands cadres que Cas2, afficher Cas3 en priorité comme Solution à Cas2

Je le concède, ça fait des boucles dans tous les sens si on veut un truc parfait, donc on oublie ça...

Mais voilà, à moins que je bug (c'est fort possible) la notion de "priorité aux grands cadres" engendre un phénomène d'algorithme "glouton" car le choix d'au moins 1 grand cadre exclu comme solution toutes les solutions qui n'utilisent pas de grand cadre. D'où le fait que la sélection entre ces 3 solutions indépendante doit se faire par un choix humain suivant un mix de justesse (valeur au plus proche du mur), de simplicité (moins de cadres à accrocher= plus simple) et esthétique (acceptation de non remplissage pour avoir une installation plus homogène)

en tout cas merci pour ta contribution ça m'aide à décortiquer le problème