h3. Rezolvare:

Din enunţ intuim că o componentă a stării trebuie să fie submulţimea participanţilor aflaţi în plută în punctul curent, intuiţie confirmată de numărul mic al participanţilor, $N ≤ 10$. Există $2^10^$ astfel de variante, din care vom exclude varianta în care pluta este goală. O stare a problemei, reprezentănd soluţia unei subprobleme, va fi alcătuită din poziţia curentă a plutei (punctul $P{~i~}$ unde se află) şi submulţimea oamenilor care se află în plută. Observăm că de la punctul precedent au coborât nişte oameni, au urcat alţii apoi pluta a continuat spre punctul curent; aceşti paşi contribuie la timpul total şi reprezintă 2 părţi ale recurenţei soluţiei. Dacă notăm cu $Tm[i][S]$ timpul minim necesar pentru a ajunge în punctul $i$ cu submulţimea $S$ a oamenilor din plută, putem descrie problema prin relaţiile:
<tex> $T[0][0] = 0$ </tex>
<tex> $T[0][S] = \infty, \forall S \neq 0$ </tex>
<tex> $T[i][0] = \infty, \forall 1 \le i \le M$ </tex>
<tex> $T[i][S] = \min_{S'} \{T[i-1][S'] + Uc[S'][S] + Dt[i][S] \}, \forall 1 \le i \le M$ \forall S \neq 0$ </tex>
unde $Uc[S'][S]$ este timpul necesar pentru urcarea şi coborârea participanţilor din plută astfel încât pornind din starea $S'$ să se ajungă în starea $S$, 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 $Uc$ şi $Dt$ sunt:
<tex> $Uc[S_1][S_2] = \sum_{i \in S_1 - S_2}{s_i} + \sum_{i \in S_2 - S_1}{s_i} $ </tex>
<tex> $Dt[i][S] = \left\{

Din enunţ intuim că o componentă a stării trebuie să fie submulţimea participanţilor aflaţi în plută în punctul curent, intuiţie confirmată de numărul mic al participanţilor ({$N ≤ 10$}). Există $2^10^$ astfel de variante, din care vom exclude varianta în care pluta este goală. O stare a problemei, reprezentănd soluţia unei subprobleme, va fi alcătuită din poziţia curentă a plutei (punctul $P{~i~}$ unde se află) şi submulţimea oamenilor care se află în plută. Observăm că de la punctul precedent au coborât nişte oameni, au urcat alţii apoi pluta a continuat spre punctul curent; aceşti paşi contribuie la timpul total şi reprezintă 2 părţi ale recurenţei soluţiei. Dacă notăm cu $T{~m~}[i][S]$ timpul minim necesar pentru a ajunge în punctul $i$ cu submulţimea $S$ a oamenilor din plută, putem descrie problema prin relaţiile:
 
<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>
 
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:
 
<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\{

\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~}$.
 

h2. Programare dinamica folosind vectori de numere intregi
h3(#problema-1). Problema 1: 'Ugly numbers':http://code.google.com/codejam/contest/dashboard?c=32015#s=p1&a=1 (Google Code Jam 2008, Round 1C)