Compréhension d'un algorithme sur le problème du sac à dos

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 :

Citation:

---

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:

---

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 ...

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é! :aie:

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:

---

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).

Merci !

Edit : signé Treuze :lol: