Discussion :

[Treuze]

Bonjour,
Je travaille sur l'algorithme du sac a dos.

On a un sac a dos de poids p et n objets ayant chacun une valeur v et un poids w

Le but est de remplir le sac a dos au maximum (sans depasser le poids p) et avec la combinaison d'objets ayant la plus grande valeur.


J ai trouve cet algo sur le net :

On notera KP(i,c) le problème réduit à i variables et à contenance c. L'idée est la suivante :

Étant donné une variable i et une contenance c, les solutions optimales de KP(i,c) sont soit :

les solutions optimales du problème à i-1 variables avec la même contenance c (KP(i-1,c)), auxquelles on ajoute xi = 0 ;
les solutions optimales du problème à i-1 variables avec la contenance c − wi (KP(i-1,c − wi)), auxquelles on ajoute xi = 1.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
pour c de 0 à W faire
  T[0,c] := 0
fin pour
 
pour i de 1 à n faire
  pour c de 0 à W faire
    si c>w[i] alors
      T[i,c] := max( T[i-1,c], T[i-1, c-w[i]] + p[i] )
    sinon
      T[i,c] := T[i-1,c]
    fin si
  fin pour
fin pour

Mais je en comprends pas quoi mettre dans le tableau et je ne comprends pas ce que represente w[i]
SI vous pouvez m aider ...

[borisd]

w[i] représente le poids de l'objet i, p[i] le cout de i.
T[i,c] est le coût optimal qu'on peut avoir en remplissant le sac avec des objets choisis parmi les i premiers tout en ayant encore une place d'au moins c dans le sac.

[Edit] J'avais écris une énorme erreur
[re-Edit] Ah non en fait, tant pis, c'est effacé!

[borisd]

A la fin de l'algorithme, T[n,W] contient la valeur (unique) des solutions optimales.
Si tu veux une solution optimale explicitement (savoir quels objets sont sélectionnés), il suffit de parcourir n éléments du tableau en commençant par la fin :

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
 
c <- W
Pour i de n à 2
Si T[i,c]=T[i-1,c] alors 
   x[i] <- 0 // i n'est pas sélectionné
Sinon
   x[i] <- 1     // i est sélectionné
   c <- c-w[i] // la valeur optimale en T[i,c] 
                   // est obtenue à partir de T[i-1,c-w[i]] + p[i]
Fin Si
Fin Pour
Si T[1,c] = p[1] alors
   x[1] <- 1
Sinon
   x[1] <- 0
Fin Si

Si plusieurs solutions optimales existent, alors on tombe pendant le parcours sur un couple (i,c) tel que T[i,c]=T[i,c-1]=T[i-1,c-w[i]]+p[i]. On a alors deux possibilités, soit x[i]=1 et on continue en (i-1,c-w[i]), soit x=0 et on continue en (i-1,c).

[charlix]

Merci !

Edit : signé Treuze