Algorithme bottom up

EDIT

Fais un copier/coller de ton code ici, ça sera plus facile pour te répondre.
Idem, ce serais plus sympa si tu copiais l'énoncé de l'exercice ici, mais c'est moins important.

Bonjour :coucou:

Citation:

Ha voici un exemple d'algorithme Bottom Up dans le cas du problème de rendu de monnais assez connu dans ce domaine

Oui mais dans le problème de rendu de monnaie, on ne cherche pas un maximum. Et ça change tout.
Car on peut morceler et définir des sous-objectifs. (analyse descendante top-down)
Ou alors faire la liste des rendus de monnaie possibles, du "moins de pièces" au "plus de pièces". (analyse ascendante bottom-up).

En conclusion, je pense que ton programme est déjà bottom-up.
La version top-down consisterait en la définition d'un maximum local.
Mais là, ça pose la question de savoir si la réunion des maximums locaux fait le maximum global. Ce dont on peut douter.

Voici un bout de code qui marche (langage Windev, proche du pseudo-code).
Je ne sais pas si ça correspond à ce que tu appelles algorithme 'Top-Down', mais àça marche, et je pense vraiment que c'est la solution la plus rapide si on a beaucoup de cases (50 ou 100 .... au lieu de 6 dans les 2 exemples).

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
67
 
 
CONSTANT
	valeur_code_defaut = -999
END
 
un_scenar  is Structure
	tb_bool is array of 100 booleans
	score is int 
	last_code is int
END
 
tb_scenar is array of 0 un_scenar
nb_cases is int
 
une_case is Structure
	valeur is int
	code is int
END
tb_cases is array of 100 une_case
 
koeff_a , koeff_b is int 
 
-- --------------- Fin des déclarations
 
-- --------------- ici , mettre le code pour initialiser les data. Par exemple nb_cases=6 ; koeff_a=-2 ; koeff_b=5   etc pour l'exemple 1.
 
kk, i,j,n is int 
ch is string
Qscenar is un_scenar
nv_scenar is un_scenar
 
 
Qscenar.last_code = valeur_code_defaut
Qscenar.score = 0
 
ArrayAddLine(tb_scenar, Qscenar)
 
FOR i = 1 _TO_ nb_cases
	n = ArrayCount(tb_scenar)
	FOR j = n TO 1 STEP -1
		Qscenar = tb_scenar[j]
		                             // TableauSupprime(tb_scenar,j)		  en fait , pas besoin de supprimer la ligne.  Cette ligne est la copie conforme que la ligne que j'ajouterais avec tb_bool[j]=0
		nv_scenar = Qscenar
		nv_scenar.tb_bool[i] = True
		nv_scenar.last_code = tb_cases[i].code	
 
		IF tb_cases[i].code = Qscenar.last_code THEN 
			kk = koeff_a 
		ELSE
			kk = koeff_b 
		END
		nv_scenar.score += kk * tb_cases[i].valeur
		ArrayAddLine(tb_scenar,nv_scenar)
	END
 
	ArraySort(tb_scenar,asMember, "+LAST_CODE;-SCORE")
	n = ArrayCount(tb_scenar)
	FOR j = n TO 2 STEP -1
		IF tb_scenar [j].last_code = tb_scenar[j-1].last_code THEN 
			ArrayDelete(tb_scenar,j)
		END
	END
END
ArraySort(tb_scenar,asMember, "-SCORE")
 
ff_dessine(tb_scenar[1])    // A ce niveau, tb_scenar est la solution optimale.

A chaque niveau, on recense les scénarios qu'on a sous le coude. On élimine les scénarios qui ne pourront pas être optimums ( si 2 scénarios ont la même valeur dans Last_Code, je garde un seul des 2, celui qui a le plus grand score dans Score.

Et à chaque niveau, on prend les différents scénarios qu'on a sous le coude, et pour chacun d'eux, on envisage 2 options (donc 2 nouveaux scénarios) : Prendre , ou rejeter la case n°i.