Conserver un chemin dans un backtracking

Version imprimable

Bonjour,

J'essaye depuis toute la journée de conserver un chemin dans mon parcours en profondeur. En effet, je m'attaque au problème du "Coin Change" et je souhaite récupérer le nombre de pièce qu'il faut pour rendre un montant quelconque.

Mon code :

Code:

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
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.concurrent.ArrayBlockingQueue;
 
public class Illimite {
 
	static double listePieces [] = {5, 2, 1};
	//static double montant = 12.35;
	static double montantTot = 10;
	static int profondeur = 50;
 
	// Pile FIFO qui contient la solution en cours
	static ArrayBlockingQueue<Double> sommet;
	static int[] sol = new int[3];
 
 
	/**
         * Fonction principale
         * @param args
         */
	public static void main (String[] args){
		Illimite p = new Illimite();
		sommet = new ArrayBlockingQueue<Double>(profondeur+1);
		try {
			sommet.put(montantTot);
			p.calcultest(sol);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
	}
 
	public void calcultest(int[] sol) {
		while(sommet.size()>0){
			System.out.println("Solution="+Arrays.toString(sol));	
			double montant = sommet.poll();
 
 
			for(int j =0;j<listePieces.length;j++){
				try {
					double next = montant-(listePieces[j]);
					System.out.println("Montant="+montant+"; NextMontant="+next);
					if(next>=0) {
						//On copie la sol precedente
						sol[j]++;
						if(next>0) {
							sommet.put(next);
							calcultest(sol);
						}
						if(next==0) {
							System.out.print("SOLUTION =");
							System.out.println(Arrays.toString(sol));
							sol[j]--;
							return;
						}
 
 
 
					}
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
		}
	}
}

Mon problème se situe ici je pense :

Code:

1
2
3
4
5
6
7
8
9
10
11
 
if(next>0) {
							sommet.put(next);
							calcultest(sol);
						}
						if(next==0) {
							System.out.print("SOLUTION =");
							System.out.println(Arrays.toString(sol));
							sol[j]--;
							return;
						}

Cela fonctionne au début mais dès que je change de branche sur mon arbre cela ne décrémente pas assez et je suis perdu. J'ai essayé de faire passer le dernier chemin en paramètre mais rien à faire...

J'ai besoin d'un petit coup de pouce.

PS: J'ai fouillé sur le forum mais impossible de trouver une réponse précise sur ma question après de multiple essai.

Merci d'avance

17/10/2011, 13h56
sinok

Bah après le calcul, il faudrait peut être penser à faire un

Code:

sommet.remove(next);

Sinon ta liste contiendra tout ton parcours et non la branche en cours...
17/10/2011, 15h53
akrogames

Coucou sinok,

Merci de regarder avec moi, c'est sympa de ta part. En fait, j'ai dans mon int[] sol la solution courante normalement. Donc pour un montant de 10 et des pièces de 5,2,1 je veux les solutions suivante :

[1,0,0]
[2,0,0] = 2 pièces de 5euro

Matrice des états :
Profondeur 0 :
Profondeur 1 : [5,8,9]
Profondeur 2 : [0,3,4,....]

Mais je fais déjà un remove avec sommet.poll() non ? Et je fais déjà un sommet.put(next); mais seulement si l'état suivant est > à 0. J'ai pas besoin de faire de remove je crois...

Merci d'avance.

Le vrai problème se situe sur la copie de ton array, ce que tu ne fais pas !

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
if(next>=0) {
						//On copie la sol precedente
						int[] newSol = Arrays.copyOf(sol,3);
						newSol[j]++;
						if(next>0) {
							sommet.put(next);
							calcultest(newSol);
						}
						if(next==0) {
							System.out.print("SOLUTION =");
							System.out.println(Arrays.toString(newSol));
							return;
						}
 					}

18/10/2011, 08h09
akrogames

Merci beaucoup Rei Ichido !

A force de rester dessus je ne faisais plus attention ! Un grand merci.