Discussion :

[cmoa59]

Bonjour a tous.

Je travaille sur un algo capable de generer toutes les combinaisons possibles d'une liste.

Je m'explique.

J'ai une liste d'elements contenant chacun 4 attributs, a savoir un identifiant et une quantite. Ils sont donc de la forme : Element(identifiant i, quantite q, prix p1, prix p2).

J'ai egalement une quantite Q qui est la quantite minimale a atteindre.

Ainsi, je dois recuperer toutes les combinaisons possibles de mes elements (je peux les prendre autant de fois que je veux) et je dois au minimum avoir ma somme des quantite des elements associes = Q. J'espere que je suis clair.

Je vous donne un cas concret:
Il me faut 13 Kg de platre. J'ai a ma disposition des sacs de 20,10,5 et 1 Kg.
Ma liste d'elements est donc :
sac1(id_sac1,q_sac1=20,p1_sac1,p2_sac1)
sac2(id_sac2,q_sac1=10,p1_sac1,p2_sac1)
sac3(id_sac3,q_sac1=5,p1_sac1,p2_sac1)
sac4(id_sac4,q_sac1=1,p1_sac1,p2_sac1)

Plusieurs combinaisons possibles sont :
- (1 sac1)
- (1 sac2 + 3 sac4)
- (1 sac2 +1 sac3)
- (13 sac1)
....

Je dois donc generer toutes les combinaisons possibles de sac pour mon probleme.
Je pensais imbriquee des boucle 'for' mais cela est rendu impossible a cause du nombre a priori inconnu de nombre maxi dans de sac dans ma combinaison.

Si vous avez des questions, posez les, je vais essayer de surveiller le topic! Merci d'avance

[iohack]

Pour minimiser/maximiser, fait une recherche sur la méthode du simplex

[cmoa59]

Ok merci, je pencherais bien sur la recursivité aussi mais j'aimerais bien avoir des conseils sur la chose...

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
 
Fonction combi(liste_article,liste_combi,combi,Qté_initiale,Qte_temp){
  SI liste_article non nulle {
    element_max = element_qte_max(liste_article);
    Qte_temp = quantite de element_qte_max;
    SI Qte_temp <= 0 {
      ajoute element_max à combi;
      ajoute combinaison à liste_combi;
      retire element_max de liste_article;
      initialisation de combi à vide;
      combi(liste_article,liste_combi,combi,Qte_init,Qte_init);
    }
    SINON {
      ajoute element_max à combi;
      combi(liste_article,liste_combi,combi,Qte_init,Qte_temp;
    }
    FINSI
  }
  SINON {
    renvoi liste_combi;
  }
  FINSI
}

Je pense à ca mais je suis pas sur que cela couvre toutes les combinaisons... pour la suite, c'est tres simple, mon probleme reside bien dans la generation des combinaisons. J'attends vos commentaires et vais regarder la methode du simplexe dont il me reste quelques souvenirs...

Merci d'avance!

[cmoa59]

Quelqu'un aurait il un exemple de simplexe, voir meme de prog du simplexe car la, malgré mes recherches, je merde un petit peu...

Alors si quelqu'un a quelque chose qui peut me faire avancer, merci d'avance

[Babaôrom]

Moi je te proposerai une simple méthode récursive: pour la quantité que tu souhaites, tu commences par chercher le plus gros sac que tu peux mettre (pas de sac de 10kg pour une quantité de 5kg demandée). Ensuite tu recommence avec le 2ème plus gros sac que tu peux mettre c'est à dire le plus gros pour la quantité qu'il te reste à fournir (Q demandée - Q du premier sac). A chaque fois que la fonction "remonte", tu passes au sac de taille en dessous et tu recommences.

Code :

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

1
2
3
4
5
6
7
8
9
10
 
maFonction(Q):
Qd=Quantité demandée
Li=Liste des sacs par ordre décroissant de quantité
 
Pour x=0 à taille de Li
 Si Li[x].Quantité > Qd
   rien
 Sinon
  maCombinaison=[Li[x],maFonction(Qd-Li[x].Quantité)]

C'est pas très bien écrit en fait mais ca serait quelquechose de ce style. Tu auras ainsi toutes les combinaisons possibles et sans doublons.

[cmoa59]

Tres bonne proposition, mais la ou c'est un peu plus compliquee, c'est que je peux avoir des doublons.

Exemple : 75 Kg avec des sacs de 50,20,10 et 5Kg

Combinaisons possibles :
(50,20,5)
(50,10,10,5)
(50,10,5,5,5)
(50,5,5,5,5,5)
(20,20,20,10,5)
(20,20,20,5,5,5)
(20,20,10,10,10,5)
(20,20,10,10,5,5,5)
(20,20,10,5,5,5,5,5)
(20,20,5,5,5,5,5,5,5)
(20,10,10,10,10,10,5)
...

Je ne vais pas jusqu'au bout car ca commence a devenir un peu long...
D'apres cet exemple, on peut imaginer a quoi va ressembler mon algo recursif (je mets le simplexe de cote par la difficulte de le mettre en place, et le manque de temps, a moins que qq1 soit capable de me forunir toutes donnees neccessaires pour ecrire le code correspondant) mais il y a pas de cas a ne pas oublier, savoir a quel rang remonter et comment...

Merci de la proposition et de ta contribution!

[Babaôrom]

Quand on peut aider!

[leminipouce]

Bonjour,

Simple petite question, cet algo a-t'il un but précis, ou est-cec seulement pour la technique ? Car dans ton exemple, je ne vois pas bien l'intérêt d'avoir des doublons...

Sinon, j'avoue galérer un peu pu trouver un moyen de mettre en oeuvre l'idée...

[cmoa59]

L'interet des doublons... tres bonne question! En fait le but de l'opération est d'arriver à minimiser le coût d'achat des produits.

C'est vrai qu'en général, ça revient moins cher d'acheter 1 sac de 50Kg que d'acheter 5 sacs de 10Kg, mais dans le cas d'une promotion, alors cette tendance peut être inversée et les 5sacs de 10Kg peuvent revenir moins cher que 1 sac de 50 Kg! C'est dans ce cas qu'il faut prevoir toutes les combinaisons, calculer le cout de chaque combinaison et prendre celle dont le coût est le plus faible. Dans le cas où nous aurions plusieurs solutions pour le minimum alors je prendrai celle qui minimise le nombre de produits.
Ex :
1 sac de 50Kg = 50€
5 sac de 10 Kg = 5 x 10€ = 50€

Alors dans ce cas je prend le sac de 50Kg car 1<5

J'espere etre clair et n'hesitez a proposer ou poser des questions. Merci

[Babaôrom]

Dans ce cas là il ne s'agit pas d'un doublon, un doublon ce serait retrouver dans ta liste finale de combinaisons:

...
(50)
(20,20,10)
(20,10,10,10)
(10,20,20)
...

Dans ce cas là tu as 2 combinaisons identiques (2eme et 4eme lignes), ce qui ne te sert à rien je pense.

[leminipouce]

C'est exactement ce que j'avais imaginer.
Et dans ce cas, je pense que ça simplifie pas mal le problème.

En effet, tu dispose déjà de couple quantité prix. Ce dernier t'autorise alors à envisager non plus toutes les combinaisons possibles et imaginables, mais seulement celles dont le couple quantité-prix est optimum !

Et dans cet optique, je peux me tromper (mais je vais y réléchir sous peu et reposter...) tu peux me semble-t'il éliminer d'office le plus gros dénominateur dès lors que son prix est supérieur à celui de son successeur direct multiplier par n pour obtenir le même poids.
Je m'explique en 2 mots. L'intérêt ici me semble-t'il est de limiter le raisonnement à une équation mathématique dans laquelle tu vasa considérer chaque dénominateur ainsi que l'ensemble de ses propres dénominateurs. Et tu commence par le plus petit de ta liste. Ainsi, de manière progressive tu vas substituer à chaque "poids" un ensemble de poids inférieur équivalent, mais moins cher.
Et tu te retrouve à reprendre la solution précédement proposée par babaôrom.

[EDIT] Je suis bien d'accord avec Babaôrom pour sa dernière remarque...
Le but de ma manip. est de savoir d'avance si il est plus intéressant ou non de remplacer (dans son dernier exemple) 20 par 10, 10 ou pas. Si OUI, alors tu supprimes tout simplement 20 de la liste...

[leminipouce]

Ensuite, mais seulement ensuite, je pense qu'il te faudra également prévoir le cas ou quelqu'un veut prendre 98Kg, que le sac de 50Kg est à 50€, celui de 20Kg à 25€ et celui de 100Kg à 90€... auquel cas il te faudra orienter l'achât vers une quantité supérieur à celle désiré pour obtenir un prix minimal.

La solution reste quand même hyper simple : quand tu as la quantité exact avec ton prix optimum, tu regardes si il est inférieur ou non à prix de la quantité directement supérieur. A priori, il est peu probable que le prix d'une quantité qui n'est pas directement supérieure soit inférieur à celui de la quantité exacte... Mais tu peux toujours faire une recherche sur l'ensemble des prix des quantités supérieures !

[leminipouce]

Et voilà l'algo auquel je pensais...

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
int prixInf=0, prixSup=0, qtSup=0, qtInf=0, nb=0;
Li.sort(Qt);    //Tri de la liste par quantité croissante
For(int=0; i<Li.length-1; i++){
    qtSup = Li[i+1];
    qtInf = Li[i];
    prixSup = Li[i+1];
    prixInf = Li[i];
 
    //On calcul le nombre de sac de la quantité inférieure nécessaires
    //pour obtenir au moins un sac de quantité supérieure
    nb = qtSup \ qtInf;
    if((nb*qtInf)<qtSup)
        nb++;
 
    //Si le prix obtenu grâcec au sac de quantité inférieur est plus avantageux
    //alors on supprime la quantité supérieure de la liste
    if((prixInf*nb)<prixSup)
        Li[i+&].remove(); //Attention, si tu fais un remove alors que tu es dans une boucle for, ça va planter
        //Je te laisse adapter l'algo en fonction. (utilise par exemple un itérateur...)
        //ou contente toi de mettre un tag dans ta liste genre boolean aUtiliser = false;
}

L'ordre de la liste est indispensable. Si elle est triée dans l'autre sens, tu es obligé de remonter d'un cran en arrière à chaque suppression !

Au fait... il existe un forum exprès pour les algo ! Ton sujet risque d'être bientôt déplacé.

[cmoa59]

Voila donc mon algo codé...
N'hesitez pas a commenter!

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
64
65
66
67
68
69
70
71
72
73
74
75
 
/* ALGO de calcul de combinaisons d'articles pour un produit */
	public static Vector combinaison(Vector pvListeArtDebut, Vector pvListeArtEnCours, Vector pvListeCombinaison,
										Vector pvCombinaison, double pnQteTotale, double pnQteRest){
 
		/* On retire de la liste des peres à traiter, l'actuel */
		if (pvCombinaison.size()>0){
			Vector vPremier = (Vector)pvCombinaison.get(0);
			if (pvListeArtDebut.size()>0){
				pvListeArtDebut.remove(vPremier);
			}
		}
		/* Si tous les peres sont traites */
		if (pvListeArtDebut != null || pvListeArtEnCours != null){
			Vector vMax = maxi(pvListeArtEnCours);
			pnQteRest = pnQteRest - ((Double)vMax.get(2)).doubleValue();
			/* Si la Qte restante est > 0 alors on ajout l'article à la liste la combinaison */
			if (pnQteRest > 0){
				pvCombinaison.add(vMax);
				combinaison(pvListeArtDebut,pvListeArtEnCours,pvListeCombinaison,pvCombinaison,pnQteTotale,pnQteRest);
			}
			/*  */
			else{
				pvListeArtEnCours.remove(vMax);
				if (pnQteRest < 0){
					if (pvListeArtEnCours.size()>=1){
						pnQteRest += ((Double)vMax.get(2)).doubleValue();
						combinaison(pvListeArtDebut,pvListeArtEnCours,pvListeCombinaison,pvCombinaison,pnQteTotale,pnQteRest);
					}
					/* On a plus d'élément disponible à ajouter et la quantité n'est pas atteinte */
					else{
						for (Enumeration eArt = pvCombinaison.elements(); eArt.hasMoreElements();){
							Vector vCombinaison = (Vector) eArt.nextElement();
							pvListeArtEnCours.remove(vCombinaison);
						}
						pvCombinaison.remove((Vector)pvCombinaison.lastElement());
						pnQteRest += ((Double)vMax.get(2)).doubleValue();
						combinaison(pvListeArtDebut,pvListeArtEnCours,pvListeCombinaison,pvCombinaison,pnQteTotale,pnQteRest);
					}
				}
				/* Cas où la quantité restante est nulle, donc une combinaison est terminée */
				else{
					pvCombinaison.add(vMax);
					pvListeCombinaison.add(pvCombinaison);
					if (pvListeArtEnCours.size()>=1){
						pvCombinaison.remove((Vector)pvCombinaison.lastElement());
						pvListeArtEnCours.remove(vMax);
						pnQteRest += ((Double)vMax.get(2)).doubleValue();
						combinaison(pvListeArtDebut,pvListeArtEnCours,pvListeCombinaison,pvCombinaison,pnQteTotale,pnQteRest);
					}
					else{
						for (Enumeration eArt = pvCombinaison.elements(); eArt.hasMoreElements();){
							Vector vCombinaison = (Vector) eArt.nextElement();
							if (vCombinaison.equals(vMax)){
								pvListeArtEnCours.remove(vCombinaison);
								pnQteRest += ((Double)vCombinaison.get(2)).doubleValue();
							}
						}
						pnQteRest += ((Double)((Vector)(pvCombinaison.lastElement())).get(2)).doubleValue();
						pvCombinaison.remove(pvCombinaison.lastElement());
						pvListeArtEnCours = pvListeArtDebut;
						Vector vTemp = null;
						for (Enumeration eArt = pvListeArtEnCours.elements(); eArt.hasMoreElements();){
							vTemp = (Vector) eArt.nextElement();
							if ((((Double)vMax.get(2)).doubleValue()<((Double)vTemp.get(2)).doubleValue()) && (((Double)(((Vector)(pvListeArtDebut.firstElement())).get(2))).doubleValue()>((Double)vTemp.get(2)).doubleValue())){
									pvListeArtEnCours.remove(vTemp);
								}
						}
						combinaison(pvListeArtDebut,pvListeArtEnCours,pvListeCombinaison,pvCombinaison,pnQteTotale,pnQteRest);
					}
				}
			}
		}
		return pvListeCombinaison;
	}

Je n'ai pas encore pu le tester car je dois resoudre un probleme de NoSuchMethodError que j'ai depuis ce matin! Je n'arrive pas a passer outre, enfin, surtout si vous voyez une erreur dans mon code, remontez la moi! Merci

[leminipouce]

Voila donc mon algo codé...
N'hesitez pas a commenter!

OK, alors premièrement, je me permettrais deux petites réflexion sur la qualité du code :

1. Tu utilises des Veccteurs de partout. Pourquoi ne pas faire une classe regroupant tous les attributs de tes articles. Ce serait plus simple à mettre en oeuvre et à maintenir d'utiliser des getQuantité() par exemple plutôt que de pvCombinaison.get(2).
2. Tes commentaires ne décrivent pas ce que tu fais/vas faire. Coupler avec des vecteurs pour tout objet, dont on ne connaît pas la stucture/le contenu, ce n'est pas très facile de comprendre ton cheminement, et ce que tu fais.

OK, le get(2) ça renvoie une quantité, mais nul part tu ne t'occupes du prix. Le but de la manoeuvre n'était-il pas de trouver le prix optimum pour une quantité souhaitée ?
A quoi te sert la partie "/* On retire de la liste des peres à traiter, l'actuel */" ?
Que fait la méthode maxi(). Sur quoi se base-t'elle ?
Que contienne chacun de tes Vecteurs ? Et pourquoi retourner pvListeCombinaison alors qu'elle est passée en paramètre ? (Rappel: Java fonctionne par référence pvListeCombinaison est donc modifiée dans la méthode appelante...)

Enfin, mais là c'est peut-être plus perso, que signifie ta nomenclature ? pv = ?, pn = ?

[cmoa59]

Ok, tres bien les remarques! En fait, dans ce cas, il s'agit juste de generer toutes les combinaisons possibles.
Le calcul des prix, je m'en occupe apres par une autre methode.

La fonction maxi() retourne l'element max.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
	public static Vector maxi(Vector pvListe){
		Vector vMaxi = (Vector)pvListe.firstElement();
		for (Enumeration eArt = pvListe.elements(); eArt.hasMoreElements();){
			Vector vTemp = (Vector) eArt.nextElement();
			if (((Double)vTemp.get(2)).doubleValue() > ((Double)vMaxi.get(2)).doubleValue()){
				vMaxi = vTemp;
			}
		}
		return vMaxi;
	}

La structure de mes vecteurs d'article est : id_article,contenance,prix

Je retourne pvListeCombinaison car je la modifie directement dans la fonction! C'est à cause de la récursivité que je fais de cette manière.

Pour ce qui est des conventions :
p -> paramètre => pn -> parametre de type nombre
n -> nombre
s -> chaine de charactere
v -> vecteur

Voila donc ce pourquoi j'ai fait de la sorte. La plus grande difficulté pour moi était vraiment de générer les combinaisons possibles. Ensuite, une fois que l'on dispose de toutes les combinaisons, il est très simple de savoir laquelle est la moins onéreuse.

[cmoa59]

Ca risque de servir un de ces jours a quelqu'un alors je poste mon algo terminal un peu plus explicité. La fonction de maxi reste la même!

Voila donc un bel algo, mis en, production et qui a l'air de bien fonctionner et donne apparemment de bons temps de réponse.

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
/* ALGO de calcul de combinaisons d'articles pour un produit en récursif */
/* l'entier pi permet de calculer le nombre d'appel de la fonction */
/* Les "pvListe" sont des listes d'articles
 * pvCombinaison est la combinaison en cours
 * pnQte sont des quantités
 * Chaque article est composé de [Id_article,Contenance,prixSansRemise,PrixAvecRemise,Quantité]
 */
public static Vector combinaison(Vector pvListeArtDebut, Vector pvListeArtEnCours, Vector pvListeCombinaison,
									Vector pvCombinaison, double pnQteTotale, double pnQteRest, int pi){
	/* On retire de la liste des peres à traiter, l'actuel */
	if (pvCombinaison.size()>0){
		Vector vPremier = new Vector((Vector)pvCombinaison.firstElement());
		if (pvListeArtDebut.size()>0){
			Vector vPere = new Vector((Vector)pvListeArtDebut.firstElement());
			if (vPremier.equals(vPere)){
				//System.out.println("On supprime l'élément de la liste : "+vPere);
				pvListeArtDebut.remove(vPere);
			}
		}
	}
	/* Si tous les peres ne sont pas traites */
	if (pvListeArtDebut.size()!=0 || pvListeArtEnCours.size()!=0){
		Vector vMax = new Vector();
		vMax = maxi(pvListeArtEnCours);
		pnQteRest = pnQteRest - ((Double)vMax.get(1)).doubleValue();
		/* Si la Qte restante est > 0 alors on ajoute l'article à la combinaison */
		if (pnQteRest > 0){
			pvCombinaison.add(new Vector(Arrays.asList(vMax.toArray())));
			/* Je relance la combinaison avec les mêmes paramètres */
			combinaison(pvListeArtDebut,pvListeArtEnCours,pvListeCombinaison,pvCombinaison,pnQteTotale,pnQteRest,pi+1);
		}
		/* La quantité restante est inférieure ou égale à 0 */
		else{
			/* Retire l'article don la quantité est maximale de la liste en cours */
			pvListeArtEnCours.remove(vMax);
			/* La quantité est dépassée */
			/* Ajout de l'élément à la combinaison */
			pvCombinaison.addElement(new Vector(Arrays.asList(vMax.toArray())));
			/* Ajout d'un combinaison à la liste de combinaison */
			pvListeCombinaison.add(new Vector(Arrays.asList(pvCombinaison.toArray())));
			/* Il reste encore des éléments à traiter dans ListeEnCours*/
			/* Je supprime le dernier inséré de la liste EnCours et je relance l'algo */
			if (pvListeArtEnCours.size()>=1){
				/* Je supprime le dernier élément inséré dans la combinaison */
				pvCombinaison.remove(vMax);
				/* Recalcul de la quantité restante */
				pnQteRest += ((Double)vMax.get(1)).doubleValue();
				/* Je relance la fonction avec les nouveaux paramètres */
				combinaison(pvListeArtDebut,pvListeArtEnCours,pvListeCombinaison,pvCombinaison,pnQteTotale,pnQteRest,pi+1);
			}
			/* Cas où il ne reste plus d'élément à insérer dans ListeEnCours */
			else{
				Vector vTempCombinaison = new Vector(Arrays.asList(pvCombinaison.toArray()));
				/* Retire de la combinaison en cours tous les éléments égaux au dernier élément inséré */
				for (int i=0;i<=vTempCombinaison.size();i++){
					if (pvCombinaison.contains(vMax)){
						pvCombinaison.removeElement(vMax);
						pnQteRest += ((Double)vMax.get(1)).doubleValue();
					}
				}
				/* Si la combinaison est non nulle */
				if (pvCombinaison.size()>0){
					/* Mise à jour de la quantité restante */
					pnQteRest += ((Double)((Vector)(pvCombinaison.lastElement())).get(1)).doubleValue();
					/* Valeur test pour la mise à jour du vecteur de liste en cours */
					double nTest = ((Double)((Vector)pvCombinaison.lastElement()).get(1)).doubleValue();
					/* Suppression du dernier élément */
					pvCombinaison.removeElement(pvCombinaison.lastElement());
					/* ListeEnCours = ListeDébut */
					pvListeArtEnCours = new Vector(Arrays.asList(pvListeArtDebut.toArray()));
					Vector vTemp = new Vector();
					Vector vTempListeArtEnCours = new Vector(Arrays.asList(pvListeArtEnCours.toArray()));
					/* Je retire de la liste en cours tous les élément dont la contenance est supérieure 
					 * à la contenance du dernier élément retiré */
					for (Enumeration eArt = vTempListeArtEnCours.elements(); eArt.hasMoreElements();){
						vTemp = (Vector) eArt.nextElement();
						if (((Double)vTemp.get(1)).doubleValue()>=nTest){
							pvListeArtEnCours.remove(vTemp);
						}
					}
				}
				/* Cas où toutes les combinaisons ont été générées */
				else {
					/* Réinitialisation des vecteurs pour éviter le NullPointerException */
					pvCombinaison = new Vector();
					pvListeArtEnCours = new Vector();
					pvListeArtDebut = new Vector();
				}
				/* Je relance la fonction avec les nouveaux paramètres */
				combinaison(pvListeArtDebut,pvListeArtEnCours,pvListeCombinaison,pvCombinaison,pnQteTotale,pnQteRest,pi+1);
			}
		}
	}
	return pvListeCombinaison;
}