<tex> $T_m[0][0] = 0$ </tex>
<tex> $T_m[0][S] = \infty, \forall S \neq 0$ </tex>
<tex> $T_m[i][0] = \infty, \forall 1 \le i \le M$ </tex>

<tex> $T_m[i][S] = \min_{S'} \{T_m[i-1][S'] + U_u[S'][S] + U_c[S'][S] + D_t[i][S] \}, \forall 1 \le i \le M, \forall S \neq 0$ </tex>

<tex> $T_m[i][S] = \min_{S'} \{T_m[i-1][S'] + T_u[S'][S] + T_c[S'][S] + T_t[i][S] \}, \forall 1 \le i \le M, \forall S \neq 0$ </tex>

unde $U{~u~}[S'][S]$ este timpul necesar pentru urcarea participanţilor care se găsesc în mulţimea $S$ dar nu fac parte din mulţimea $S'$, $U{~c~}[S'][S]$ este timpul necesar pentru coborârea participanţilor din plută, iar $Dt[i][S]$ este timpul necesar traversării curentului de la punctul $i-1$ la punctul $i$ dacă în plută se află participanţii din $S$. Formulele pentru valorile $U{~u~}$, $U{~c~}$ şi $D{~t~}$ sunt:

unde $T{~u~}[S'][S]$ este timpul necesar pentru urcarea participanţilor care se găsesc în mulţimea $S$ dar nu fac parte din mulţimea $S'$, $T{~c~}[S'][S]$ este timpul necesar pentru coborârea participanţilor din plută, iar $T{~t~}[i][S]$ este timpul necesar traversării curentului de la punctul $i-1$ la punctul $i$ dacă în plută se află participanţii din $S$. Formulele pentru valorile $T{~u~}$, $T{~c~}$ şi $T{~t~}$ sunt:

<tex> $U_u[S_1][S_2] = \sum_{i \in S_2 - S_1}{s_i}$ </tex>
<tex> $U_c[S_1][S_2] = \sum_{i \in S_1 - S_2}{s_i}$ </tex>
<tex> $D_t[i][S] = \left\{

<tex> $T_u[S_1][S_2] = \sum_{i \in S_2 - S_1}{s_i}$ </tex>
<tex> $T_c[S_1][S_2] = \sum_{i \in S_1 - S_2}{s_i}$ </tex>
<tex> $T_t[i][S] = \left\{

\begin{array}{l l}
  D_i & \quad \sum_{j \in S}{w_j} > c_i\\
  d_i & \quad \sum_{j \in S}{w_j} \le c_i\\
\end{array} \right. $</tex>

În formula pentru $T{~m~}[i][S]$, observăm că $D{~t~}[i][S]$ nu depinde de argumentul funcţiei de minimizare, adică de starea iniţială, deci putem scoate valoarea în afara funcţiei. Valoarea pe care căutăm s-o minimizăm este deci $T{~m~}[i-1][S'] + U{~u~}[S'][S] + U{~c~}[S'][S]$. Calcularea directă a soluţiei pe baza recurenţelor de mai sus are complexitatea $O(M*N*2^N^ + M*2^N^*2^N^)$. Primul termen al complexităţii este dat de calcularea valorilor $D{~t~}$, iar al doilea de calcularea matricii $T{~m~}$.

În formula pentru $T{~m~}[i][S]$, observăm că $T{~t~}[i][S]$ nu depinde de argumentul funcţiei de minimizare, adică de starea iniţială, deci putem scoate valoarea în afara funcţiei. Valoarea pe care căutăm s-o minimizăm este deci $T{~m~}[i-1][S'] + T{~u~}[S'][S] + T{~c~}[S'][S]$. Calcularea directă a soluţiei pe baza recurenţelor de mai sus are complexitatea $O(M*N*2^N^ + M*2^N^*2^N^)$. Primul termen al complexităţii este dat de calcularea valorilor $T{~t~}$, iar al doilea de calcularea matricii $T{~m~}$.

h2. Programare dinamica folosind vectori de numere intregi