Discussion :

[akrogames]

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

[sinok]

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

Code :

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

sommet.remove(next);

Sinon ta liste contiendra tout ton parcours et non la branche en cours...

[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.

[Rei Ichido]

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

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
 
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;
						}
 					}

[akrogames]

Merci beaucoup Rei Ichido !

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