Discussion :

[ahmadou_20]

Salut les gars,

J ai implemente une premiere version (tres basique et tres simple) d un algo de programmation dynamique du probleme du sac a dos. Mais j ai pas compris pourquoi une exception de NullPointer est levee a chaque fois (ligne 33).

Help please !!!

Ci dessous le code que j ai ecrit :

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
 
Integer[] values = new Integer[100];
 Integer[] weights = new Integer[100];
 
    values[1] = 2;
    values[2] = 2;
    values[3] = 3;
    values[4] = 1;
    weights[1] = 1;
    weights[2] = 2;
    weights[3] = 1;
    weights[4] = 2;
 
    Integer C = 6;
 
    int n = 4;
 
 
 
    Integer[][] tableau = new Integer[100][100];
 
 
    for(int v = 1; v <= C; v++) {
      tableau[v][0] = 0;
    }
 
    for(int i = 1; i <= n; i++) {
      for(int v = 0; v <= C; v++) {
        if(v < weights[i]) {
          tableau[v][i] = tableau[v][i - 1];
        }
        else {
          tableau[v][i] = Math.max(tableau[v][i - 1], tableau[v - weights[i]][i - 1] + values[i]);
        }
      }
    }
 
    System.out.println("Valeur optimale" + tableau[C][n]);
 
    Integer[] x = new Integer[n + 1];
 
    for(int i = 0; i <= n; i++) {
      x[i] = 0;
    }
 
    int k = n;
    while(C > 0 || k > 0) {
      if(tableau[C][k] != tableau[C][k - 1]) {
        x[k] = x[k] + 1;
        C = C - weights[k];
      }
      k--;
    }
 
    System.out.println("On va prendre le(s) objet(s) : ");
 
    for(int j = 1; j <= n; j++) {
      if(x[j] == 1) {
        System.out.println("Object " + j);
 
      }
    }

Merci d avance pour votre aide.

[tchize_]

lorsque i=1 et v=1

weights[i]=1

donc v-weights[i] = 0

et donc tu lit tableau[v-weights[i]][i-1], c'est à dire tableau[0][0] mais tu n'a jamais rien stocké dans cette case, donc tu te chope un null, qu'il est impossible de transformer en int pour le faire intervenir dans ton calcul => erreur.


Solution: initialise proprement ton tableau plutot que d'y mettre des null partout. Voir, remplace Integer par int, car je ne vois pas ici l'intérêt d'utiliser les objets plutôt que les int.

[ahmadou_20]

Merci C est fait et ca marche (enfin presque !!!).

Sauf que un autre probleme surgit cette fois.

Un probleme de ArrayIndexOutOfBounds que je n avais pas avant (je m en suis rendu compte en modifiant values[4] de 1 a 7 par exemple) : je comprends pas trop ce qui se passe ici !!!

Le dernier 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
 
 
Integer[] values = new Integer[100];
 Integer[] weights = new Integer[100];
 
    values[1] = 2;
    values[2] = 2;
    values[3] = 3;
    values[4] = 7;
    weights[1] = 1;
    weights[2] = 2;
    weights[3] = 1;
    weights[4] = 2;
 
    Integer C = 6;
 
    int n = 4;
 
 
 
    Integer[][] tableau = new Integer[100][100];
 
 
    for(int v = 1; v <= C; v++) {
      tableau[v][0] = 0;
    }
 
    for(int i = 1; i <= n; i++) {
      for(int v = 0; v <= C; v++) {
        if(v < weights[i]) {
          tableau[v][i] = tableau[v][i - 1];
        }
        else {
          tableau[v][i] = Math.max(tableau[v][i - 1], tableau[v - weights[i]][i - 1] + values[i]);
        }
      }
    }
 
    System.out.println("Valeur optimale" + tableau[C][n]);
 
    Integer[] x = new Integer[n + 1];
 
    for(int i = 0; i <= n; i++) {
      x[i] = 0;
    }
 
    int k = n;
    while(C > 0 || k > 0) {
      if(tableau[C][k] != tableau[C][k - 1]) {
        x[k] = x[k] + 1;
        C = C - weights[k];
      }
      k--;
    }
 
    System.out.println("On va prendre le(s) objet(s) : ");
 
    for(int j = 1; j <= n; j++) {
      if(x[j] == 1) {
        System.out.println("Object " + j);
 
      }
    }

Merci encore une fois.

[tchize_]

ben tu regarde ton message d'erreur, tu regarde la ligne indiquée, et tu aura toutes les information nécessaires: la tableau concerné, l'index auquel tu essaie d'accéder et le fait que cette combinaison sort de la taille du tableau.

[ahmadou_20]

c est bon merci
c est resolu