Discussion :

[ahmadou_20]

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 :

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

[tchize_]

Code :

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

(tab[C][k] != tab[C][k - 1])

Tu compare les deux cases du tableau, donc des objets Float, mais deux Float peuvent contenir la même valeur float sans être la mêm instance.

Il ne faut pas comparer les instances mais les valeurs, avec equals().

Ce problème n'arriverais pas si tu utilisais plutot des float

Le problème n'apparait pas avec les Integer parce que tu as de la chance. L'autoboxing avec des int en Integer < 127 et > -128 garantis que les instances sont les mêmes. Il n'y a pas de telle garantie avec les Float.

[ahmadou_20]

Ah oui que je suis bete !!

Comment j ai pu rater ca ?

Merci bcp encore une fois !!!