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 : 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
 
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 : Sélectionner tout - Visualiser dans une fenêtre à part
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