Discussion :

[devhercule]

Bonjour,

J'utilise le solveur de contraintes Choco, et j'ai un problème à résoudre

étant donné un tableau T de n entiers, retourner toutes les combinaisons possibles dont la sommes des entiers retournées est egale à X

exemple:

tab=[5 3 8 13 1 2 9 4], X=13
les solutions possibles sont :
• 13
• 8+5
• 9+4
• 8+3+2
• Etc…

et c'est en utilisant Choco, j'ai commencer à y reflechir mais je suis bloqué mnt, voici un bout du code qui fonctionne pas mais qui pourrait aider.

Model m = new CPModel();

int [] T = {.....};

IntegerVariable[] vars = new IntegerVariable[5];

for (int i = 0; i < 5; i++)
vars[i] = Choco.makeIntVar("p" + i, l'ensemble de valeur de T);

m.addConstraint(Choco.leq(Choco.sum(vars), 13));

Merci d'avance pour votre aide

[wax78]

et c'est en utilisant Choco, j'ai commencer à y reflechir mais je suis bloqué mnt, voici un bout du code qui fonctionne pas mais qui pourrait aider.

Et donc la question est ?

(ton code la n'est pas vraiment complet non plus)

A tout fin utile, voici un exemple qui résouds le problème (mais qui a mon avis ne respecte pas tout ce qu'il devrait....)

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
	int solution = 13;
		int[] varsM = new int[] {5, 3, 8, 13, 1, 2, 9, 4};
 
		for (int k = 1; k < varsM.length; k++)
		{
			System.err.println("Nombre de termes : "+k);
			Model m = new CPModel();
			Solver s = new CPSolver();
 
			IntegerVariable[] vars = Choco.makeIntVarArray("Vars", k, varsM);
			m.addConstraint(Choco.allDifferent(vars));
			m.addConstraint(Choco.eq(solution, Choco.sum(vars)));
 
			s.read(m);
			s.solve();
			if (s.isFeasible())
			{
				int cpt =1;
				do
				{
					System.out.print((cpt++)+ " - "+ solution+" = " + s.getVar(vars[0]).getVal());
					for (int i = 1; i < vars.length; i++)
					{
						System.out.print(" + " + s.getVar(vars[i]).getVal());
					}
					System.out.println();
				}
				while (s.nextSolution()!=false);
			} else
				System.err.println("Impossible");
		}

[devhercule]

Merci comme meme

c'est pas exactement ce que je cherche, mais ça peut etre une bonne piste.

j'ai pensé à ajouter le 0 dans le tableau, et ca marche mieux en donnant toutes les combinaisons possibles. puisque il trouve 0 :
int[] varsM = new int[] {5, 3, 8, 13, 1, 2, 9, 4, 0};

Pour améliorer le résultat est ce que tu peux m'aider pour assurer ces deux contraintes:

1) un entier ne doit figurer ds la solution qu’une seule fois au max (sauf le zero bien sur, il peut se repeter) -normallement alldifferent-
2) l'ordre des entiers n'intervient pas ds la solution : exp: 4=1,0,0,3 et 4= 1,3,0,0 et 4=0,0,3,1 ... représentent la même solution.

Merci bcp pour votre aide, c tré gentl

[wax78]

Pour le point

1) oui Alldifferent semble fonctionner (comme tu px le voir dans mon code que j'ai reposté 1 minutes avant que tu écrives), mis a part pour l'histoire du 0 (entre nous ca ne sert a rien d'avoir le 0 mais bon admettons)
2) aucune idée je ne suis pas dutout specialiste de choco, jme suis juste amusé avec quelques fois pour résoudre des petits truc du genre du tiens.

[devhercule]

Nickel

Je suis d'accord avec toi pa rapport au truc de l'ajout de 0. c'était util avant ta modification.

ca resoud le premier problème et ça donne les résultats souhaités, merciiiiii

Il ne me reste que l'ordre des termes retournés pour chaque solutions, ca peut etre resolu en imposant que l'indice des entiers retournés soit croissant.

si tu peux introduir cette nouvelle contrainte ds le code je serais très reconnaissant, sinon merciiiiiiiiii bcp

[wax78]

Je pense que tu abuses un peu la, je ne suis pas non plus la pour faire ton travail

Un indice : increasingSum devrait faire toutes les contraintes d'un coup.

Edit : A essayer, car ca fonctionne, mais apres 3 termes ca ne boucle dans le vide donc je me pose des question aussi mtn