începeţi de la punctul de $P{~0~}$ cu tot grupul pe mal şi trebuie să terminaţi la punctul $P{~M~}$ cu toţi participanţii şi pluta pe mal. Nu aveţi voie să părăsiţi pluta la început sau într-un un punct intermediar şi să mergeţi pe jos spre linia de sosire fără ea. Aveţi posibilitatea să urcaţi tot grupul de salvare în plută, dar nu puteţi lăsa pluta goală în timpul călătoriei printr-un curent.
Sarcina voastră este să calculaţi timpul minim necesar pentru a ajunge la linia de sosire.

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] = \{
\begin{array}{l l}
  D_i & \quad \mbox{daca $\sum_{j \in S}{w_j} > c_i$}\\
  d_i & \quad \mbox{altfel}\\
\end{array} $</tex>

h2. Programare dinamica folosind vectori de numere intregi