1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| -- Algorithme Recursive-DP(N,C) --
Partitionner N en deux ensembles disjoints N1 et N2 de taille équivalentes
Appeler SOLVE(N1, C) pour obtenir z*(N1, c) pour tout c dans {0,...,C}
Appeler SOLVE(N2, C) pour obtenir z*(N2, c) pour tout c dans {0,...,C}
Trouver C1, C2 tels que C1+C2=C et z*(N1,C1)+z*(N2,C2) = z*(N,C)
si |N1| = 1 alors
fusionner X*(N1,C1) et X*(N*,C*) en X*(union(N1,N*), C1+C*)
N* = union(N*,N1)
C* = C* + C1
fin si
si |N2| = 1 alors
fusionner X*(N2,C2) et X*(N*,C*) en X*(union(N2,N*), C2+C*)
N* = union(N*,N2)
C* = C* + C2
fin si
si |N1| > 1 alors appeler Recursive-DP(N1,C1)
si |N2| > 1 alors appeler Recursive-DP(N2,C2) |
Partager