Programmtion dynamique - Sac a dos

Version imprimable

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:

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.

25/08/2014, 18h32
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.

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:

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.

26/08/2014, 08h54
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.
26/08/2014, 09h33
ahmadou_20

c est bon merci
c est resolu