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

[devhercule]

si j'avais la solution j'aurais pas demandé l'aide, je suis pas expert du domaine donc il vaut mieux demander les connaisseurs et c ce que je fais

merciiii je vais essayer ca

[wax78]

Sauf que j'y connais rien, je lis la doc ^^.

Je poste quand meme le code mais je dis !WARNING! car je ne suis vraiment pas sure de mon coup au vu des resultats :

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
int solution = 13;
		int[] varsM = new int[] {5, 3, 8, 13, 1, 2, 9, 4};
		IntegerVariable sum = Choco.makeIntVar("s", 13, 13);
 
		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)));
 
			m.addConstraint(Choco.increasingSum(vars, sum));
 
			s.read(m);
			s.solve();
			if (s.isFeasible())
			{
				int cpt =1;
				do
				{
					System.err.print((cpt++)+ " - "+ solution+" = " + s.getVar(vars[0]).getVal());
					for (int i = 1; i < vars.length; i++)
						System.err.print(" + " + s.getVar(vars[i]).getVal());
					System.err.println();
				}
				while (s.nextSolution()!=false);
			} else
				System.err.println("Impossible");
		}

et une autre avec une la fonction increasingNValue

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
public static void main(String args[])
	{
		int solution = 13;
		int[] varsM = new int[] {5, 3, 8, 13, 1, 2, 9, 4};
		IntegerVariable sum = Choco.makeIntVar("s", 1, 7);
 
		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)));
			//	m.addConstraint(Choco.increasingSum(vars, sum));
			m.addConstraint(Choco.increasingNValue(sum, vars));
 
			s.read(m);
			s.solve();
			if (s.isFeasible())
			{
				int cpt =1;
				do
				{
					System.err.print((cpt++)+ " - "+ solution+" = " + s.getVar(vars[0]).getVal());
					for (int i = 1; i < vars.length; i++)
						System.err.print(" + " + s.getVar(vars[i]).getVal());
					System.err.println();
				}
				while (s.nextSolution()!=false);
			} else
				System.err.println("Impossible");
		}
	}

mais il faudrait un expert pour eclairez nos lanternes (j'aime bien choco dans le principe, dommage de ne pas mieux le maitriser)

[Robin56]

si j'avais la solution j'aurais pas demandé l'aide, je suis pas expert du domaine donc il vaut mieux demander les connaisseurs et c ce que je fais

Il faut demander à des gens qui connaissent pour s'aiguiller ou se débloquer, pas pour faire le travail à ta place.

Et quand je lis cette phrase :

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

Ça ressemble plus à de la demande à faire son travail qu'à des soucis techniques.

[devhercule]

Merci wax78
Je vais essayer ca et bon weekend

[devhercule]

Bonjour
@ wax : j'ai repris votre code, j'avais besoin de quelques trucs et ça m'a énormément aider.
Par contre, j'ai une petite remarques
m.addConstraint(Choco.allDifferent(vars)); n'est pas la bonne solution car dans le cas ou on aura deux cases dans le tableau, il va éliminer une, or on doit les considérer différemment.

est ce qu'on peut appliquer alldifferent sur l'indice de la case recupérée et non pas sur la valeur,

i need help pls

thank you

[fraisa1985]

A mon avis, ce que vous voulez faire n'est pas faisable
essayez de reformuler votre pb ça sera plus simple