Probleme du sac a dos avec des valeurs en Float
Bonjour,
J ai ecrit un petit programme pour resoudre le probleme du sac a dos en utilisant la programmation dynamique.
Lorsque les valeurs des objets (values dans le code ci dessous) sont entieres, ca marche parfaitement.
mais a partir du moment ou je les change en float, il me retourne la bonne valeur optimale (10 dans le cas presente ci dessous) mais pas les bons objets (2, 3 et 4 au lieu de 1, 2 et 3).
J arrive pas a comprendre qu est ce ca a change le fait de travailler avec des float (j ai fait plein de tests mais je suis un peu bloque ici).
merci bcp de votre aide !!
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
|
int n = 4;
Float[] values = new Float[n + 1];
int[] weights = new int[n + 1];
values[1] = 5f;
values[2] = 3f;
values[3] = 2f;
values[4] = 1f;
weights[1] = 3;
weights[2] = 2;
weights[3] = 1;
weights[4] = 4;
int C = 8;
Float[][] tab = new Float[C + 1][n + 1];
for(int v = 0; v <= C; v++) {
tab[v][0] = 0f;
}
for(int i = 1; i <= n; i++) {
for(int v = 0; v <= C; v++) {
if(v < weights[i]) {
tab[v][i] = tab[v][i - 1];
}
else {
tab[v][i] = Math.max(tab[v][i - 1], tab[v - weights[i]][i - 1] + values[i]);
}
}
}
System.out.println("Valeur optimale " + tab[C][n]);
int[] x = new int[n + 1];
for(int i = 1; i <= n; i++) {
x[i] = 0;
}
int k = n;
while(C > 0 && k > 0) {
if(tab[C][k] != tab[C][k - 1]) {
x[k] = x[k] + 1;
C = C - weights[k];
}
k--;
}
System.out.println("Selected Objects : ");
for(int j = 1; j <= n; j++) {
if(x[j] == 1) {
System.out.println("Object " + j + " Value " + values[j]);
}
} |
