Math
Sac à dos : la gloutonnerie contre la table
Choisissez des colis numérotés sous une limite de masse. Comparez avec le glouton et l’optimum, puis ouvrez une cellule et remontez vers le choix optimal.
Ce qui se passe
Choisissez des colis numérotés sous une limite de masse. Comparez avec le glouton et l’optimum, puis ouvrez une cellule et remontez vers le choix optimal. T(i,c) : meilleure valeur parmi les i premiers objets avec une capacité c. Cliquez une cellule : bleu ignore, vert prend. Les flèches changent de page. w = masse, v = valeur. La taille est décorative ; seule la masse totale est limitée. La borne fractionnaire permet de diviser les objets. C’est une borne supérieure, pas un choix admissible en 0/1.
Équations du module
Équations
0/1 : sum(w_i x_i) <= W ; max sum(v_i x_i), x_i dans {0,1}
T(0,c) = 0
w_i > c: T(i,c) = T(i-1,c)
w_i <= c: T(i,c) = max(T(i-1,c), v_i + T(i-1,c-w_i))
v_i/w_i ↓; i ↑
F_greedy <= F_0/1 <= F_fractional
V_single = max({0} ∪ {v_i : w_i <= W})
max(F_greedy, V_single) >= F_0/1 / 2
N_DP = n*W; N_subsets = 2^n
