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