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 pluta a traversat curentul, au urcat nişte oameni apoi au coborât alţii; 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:

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] = T_u[0][S], \forall S \neq 0$ </tex>

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

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

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'$ (aceşti participanţi alcătuiesc mulţimea $S{~u~}$), $T{~c~}[S'][S]$ este timpul necesar pentru coborârea participanţilor din plută (participanţii din mulţimea $S{~c~}$), 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:

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

Valoarea rezultatului nu depinde de ordinea în care urcă şi coboară participanţii din plută, deci o putem alege noi. Dacă aranjăm ordinea în doi paşi astfel încât în primul pas doar să urce, apoi în al doilea pas doar să coboare, vom obţine o îmbunătăţire semnificativă a timpului de execuţie. Se observă că dacă am efectua doar adăugări de elemente (daca în plută s-ar putea doar urca persoane, fără să poată coborî), atunci <tex> $S' \in S$ </tex> şi deci reprezentarea în cod binar a mulţimii $S'$ ar avea o valoare mai mică decât reprezentarea binară a mulţimii $S$. Dacă ar avea voie doar să coboare persoane, relaţia ar fi inversă. De aceea, vom ordona operaţiile de urcare şi coborâre astfel încât să aibă loc întâi toate urcările (astfel încât să putem parcurge crescător valorile binare ale mulţimilor) apoi toate coborârile (astfel încât să putem efectua a doua parcurgere, în ordine descrescătoare). Introducem matricea auxiliară $T{~um~}[i][S]$ care reprezintă timpul minim necesar la care se poate afla pluta în punctul $i$ cu mulţimea $S$ de oameni, dacă după ultima traversare nu a coborât încă nici o persoană. Starea $S$ a fost obţinută prin una sau mai multe urcări de persoane în plută sau direct prin traversarea curentului. Recurenţele pentru $T{~um~}[i][S]$ sunt:
 
<tex> $T_{um}[i][S] = \min \left(T_m[i-1][S] + T_t[i][S], \min_{j \in S}\{T_{um}[i][S - j] + s_j\} \right) </tex>
<tex> $T_m[i][S] = \min \left(T_{um}[i][S], \min_{j \not\in S}\{T_m[i][S \cup j] + s_j\} \right) </tex>
 
Am eliminat calcularea matricilor $T{~u~}$, $T{~c~}$. Toate matricile rămase au dimensiunea $Mx2^N^$ iar calcularea fiecărui element necesită un timp $O(N)$, deci soluţia astfel obţinută are complexitatea $O(M*N*2^N^)$.
 
== code(cpp)    |
    iniţializează toate T_m[0];
    pentru i = 1, M execută
        calculează toate Tt[i];
        pentru fiecare S în ordine crescătoare a reprezentării binare execută
            Tum[i][S] = Tm[i-1][S] + Tt[i][S];
            pentru fiecare j din S execută
                Tum[i][S] = min(Tum[i][S], Tum[i][S - j] + s[j]);
            sfârşit pentru;
        sfârşit pentru;
        pentru fiecare S în ordine descrescătoare a reprezentării binare execută
            Tm[i][S] = Tum[i][S];
            pentru fiecare j care nu există în S execută
                Tm[i][S] = min(Tm[i][S], Tm[i][S + j] + s[j]);
            sfârşit pentru;
        sfârşit pentru;
    sfârşit pentru;
    returnează Tm[M][0];
==
 
Mai există două optimizări de spaţiu pe care le putem efectua în soluţia prezentată. Putem elimina matricea $T{~um~}$, calculând toate valorile direct pe matricea $T{~m~}$, deoarece aceasta va fi parcursă în ambii paşi în câte o singură direcţie. A doua optimizare se bazează pe observaţia că nu avem niciodată nevoie de alte linii în afară de ultimele 2 ($i$ si $i-1$), deci putem înlocui matricea cu 2 vectori de dimensiune $2^N^$. Valorile $T{~t~}$ pot fi calculate în cadrul primei bucle, reducând astfel spaţiul necesar soluţiei la $O(2^N^)$.

Pentru valoarea rezultatului nu este important în ce ordine urcă şi coboară participanţii din plută, deci putem alege noi ordinea. Dacă aranjăm ordinea în doi paşi astfel încât în primul pas să urcăm participanţi, apoi în al doilea pas doar să coborâm participanţi, vom obţine o îmbunătăţire semnificativă a timpului de execuţie. Se observă că dacă am efectua doar adăugări de elemente (daca în plută s-ar putea doar urca persoane, fără să poată coborî), atunci <tex> $S' \in S$ şi deci reprezentarea în cod binar a mulţimii $S'$ ar avea o valoare mai mică decât reprezentarea binară a mulţimii $S$. Dacă ar avea voie doar să coboare persoane, relaţia ar fi inversă. De aceea, vom ordona operaţiile de urcare şi coborâre astfel încât să aibă loc întâi toate urcările (astfel încât să putem parcurge crescător valorile binare ale mulţimilor) apoi toate coborârile (astfel încât să putem efectua a doua parcurgere, în ordine descrescătoare). Introducem două noi matrici auxiliare, $T{~ucm~}[i][S]$ şi $T{~um~}[i][S]$ care reprezintă timpul minim necesar la care se poate porni cu pluta de la punctul $i-1$ după ce au schimbat toţi locurile,