Solutia problemei Valoare
Multumim lui 
Vom folosi un rationament inductiv. Notam cu f(k) cea mai mare suma care poate fi atinsa (si toate mai mici decat ea) folosind k monede.
- Pasul I: f(1) este 1 daca exista elementul 1 in vectorul dat, altfel este 0;
- Pasul II: Stim f(k) si vrem sa aflam f(k + 1). Presupunem ca f(k) = s, adica putem obtine toate sumele 1, 2, ..., s folosind k monede. Ce sume putem obtine cu k + 1 monede?
Sa presupunem ca alegem o moneda cu valoare v. Atunci noi vom putea plati toate sumele 1, 2, ..., s, v, 1 + v, 2 + v, ..., s + v. Stim ca prima jumatate a sirului este consecutiva, la fel si a doua. Deci ne ramane doar sa ne asiguram ca nu exista "gauri" intre s si v, adica s + 1 < v. In concluzie, la fiecare pas trebuie sa luam moneda cu cea mai mare valoare v, astfel incat v ≤ s + 1, dupa care s creste cu v. Putem obtine aceasta valoare fara sa ne chinuim prea mult, in O(logN) folosind un arbore echilibrat, sau un container STL precum multiset, aducand solutia finala la una de complexitate O(N * logN).
O alta solutie incepe cu sortarea vectorului dat. Chiar daca complexitatea finala nu poate fi redusa, din cauza acestei sortari initiale*, solutia este liniara (dupa sortare). O voi prezenta cu scop didactic:
Vom retine o stiva (la inceput goala), in care vom adauga pe parcurs valorile din vectorul initial. Sa presupunem ca ne aflam, din nou, la pasul k + 1 si vrem sa aflam valoarea v potrivita. Vom adauga in stiva noastra toate valorile mai mici sau egale cu s + 1. Observatie: Deoarece s creste la fiecare pas, este suficient sa adaugam fiecare valoare o singura data in stiva. La final, rezultatul nostru va fi, de fapt, varful stivei, pe care il scoatem. Cum vectorul este sortat crescator, iar noi adaugam elemente in stiva de la stanga la dreapta, ea va ramane mereu crescatoare. Cum fiecare element este adaugat si eliminat o singura data, pasul acesta este de complexitate amortizata liniara. Complexitatea totala a algoritmului va fi cea data de algoritmul de sortare.
*Presupunem folosirea unei metode de sortare precum QuickSort sau MergeSort. Cititorul poate, desigur, sa foloseasca si metode mai eficiente precum Radix Sort, dar nu acesta este scopul editorialului :).
