[ALGO] Complexite des algorithmes (10)

Rappel dernier cours

Soit le nombre de parenthesages de

P(1) = 1
P(2) = 1
P(3) = 2
P(4) = 5
P(5) = 14

On fait figurer le dernier parenthesage qui sera effectue :

A1 (A2 A3 A4 A5) = 1 x 5
(A1 A2)(A3 A4 A5) = 1 x 2
(A1 A2 A3)(A4 A5) = 2 x 1
(A1 A2 A3 A4) A5 = 5 x 1

P(6) = 42

A1 (A2 A3 A4 A5 A6) = 1 x 14
(A1 A2)(A3 A4 A5 A6) = 1 x 5
(A1 A2 A3)(A4 A5 A6) = 2 x 2
(A1 A2 A3 A4)(A5 A6) = 5 x 1
A1 (A2 A3 A4 A5 A6) = 14 x 1

Nombre de Catalan



1 2 3 4 5
1 0 1200 540 640 840
2 0 240 390 640
3 0 80 260
4 0 100
5 0




:

:

:

:

Proprietes des problemes ou la programmation dynamique doit marcher

Probleme =
Solution optimale =
Sous-probleme :
Solution optimale :
etc

Il y a un chevauchement de sous-problemes possibles (justifie le cache)

Algorithme poissons

Soient n poissons de poids et d’apports caloriques .

Comment maximiser le nombre de calories qu’on peut mettre dans un sac de kg ?

Notons le nombre de cal max qu’on peut mettre dans un sac de kg en choisissant parmi les n premiers poissons



si

= on prend le poisson n
= on ignore le poisson n

Exemple


n/k 0 2 4 6 8 10
0 0 0 0 0 0 0
1 0 6 6 6 6 6
2 0 6 10 16 16 16
3 0 6 10 16 18 22