Bonjour,

Je commence directement par calmer ceux qui vont crier au scandale là-dessus : ouais j'ai cherché sur le forum. Et j'ai cherché un moment aussi sur le net, pour trouver des algo gloutons et de la programmtion dynamique.
Cependant, j'ai un cas un peu différent ou du moins, je n'arrive pas à retranscrire ce que j'ai trouvé pour gérer ce cas.

Comme pour toutes les personnes qui ont eu à faire cet exo, le but est donc de simuler un rendu de monnaie, en ayant un nombre de pièces limité.
TODO :
  1. Faire un rendu de monnaie avec un minimum de pièces (optimal quoi, genre pour 2.50€, une pièce de 2 et une de 0.50)
  2. Faire un rendu de monnaie avec un maximum de pièces (ex pour 2.50€ : 4x0.01 + 3x0.02 + 4x0.10 + 5x0.20 + 2x0.50 )

Le 1er est OK, même si j'avais fait ni gloutonnerie ni DP, j'm'en suis sorti.
Mais pour le 2ème, j'sais juste pas par quoi commencer.


Pour les codeurs Java : https://github.com/MickaelBenes/coin...exec/Main.java

Je suppose que la soluce (pour le minimum, le maximum fonctionne juste pas) n'est pas optimale mais bon ça fonctionne. Après j'ai trouvé ça :
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
67
68
69
70
public static void main( String[] args ) {
		// INPUT: valeurs et nombre de pieces disponibles
		int[] values = new int[] { 200, 100, 50, 20, 10, 5, 2, 1 };
		int[] dispos = new int[] { 0, 0, 10, 10, 0, 0, 0, 10 };
 
		// INPUT: valeur a rendre
		int entry = 80;
 
		// resolution du problème
		int[] solution = solve(values, dispos, entry);
		if (solution != null) {
			System.out.print(Arrays.toString(solution));
		} else {
			System.out.println("pas de solution");
		}
	}
 
	public static int[] solve(int[] values, int[] dispos, int remainder) {
 
		// sauvegarde de la meilleure solution
		int bestscore = Integer.MAX_VALUE;
		int[] bestsolution = null;
 
		// recherche des solutions possibles
		int[] solution = new int[values.length];
		int index = 0, score = 0;
 
		while (index >= 0) {
 
			// glouton à partir de la position courante
			// avec une sortie immediate si on depasse le meilleur score
			while (index < values.length && score < bestscore) {
				solution[index] = Math.min(remainder / values[index], dispos[index]);
				remainder -= solution[index] * values[index];
				score += solution[index];
				index++;
			}
			index--;
 
			// c'est une meilleure solution : on la conserve.
			if (remainder == 0 && score < bestscore) {
				bestscore = score;
				bestsolution = Arrays.copyOf(solution, solution.length);
			}
 
			// **** backtrack *** //
 
			// annulation de la derniere opération effectuée
			score -= solution[index];
			remainder += values[index] * solution[index];
			solution[index] = 0;
 
			// recherche de la derniere selection non nulle
			while (index >= 0 && solution[index] == 0) {
				index--;
			}
 
			if (index < 0) break;
 
			// decrémente la selection
			score--;
			remainder += values[index];
			solution[index]--;
 
			// poursuit l'exploration a partir de la position suivante
			index++;
		}
 
		return bestsolution;
	}
Qui du coup lui est optimal, mais ne me permet d'effectuer que le premier cas.

Comment faire pour le deuxième ?

Merci.