| Fişierul intrare/ieşire: | rucsac.in, rucsac.out | Sursă | Arhiva Educationala |
| Autor | Arhiva Educationala | Adăugată de |  Gavrila Vlad •GavrilaVlad |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Problema rucsacului
Se da o multime formata din N obiecte, fiecare fiind caracterizat de o greutate si un profit. Sa se gaseasca o submultime de obiecte astfel incat suma profiturilor lor sa fie maxima, iar suma greutatilor lor sa nu depaseasca o valoare G.
Date de intrare
Pe prima linie a fişierul rucsac.in se vor gasi valorile N si G, cu semnificatia din enunt. Pe urmatoarele N linii se vor gasi perechile de valori Wi si Pi, reprezentand greutatea, respectiv profitul obiectului i.
Date de ieşire
În fişierul de ieşire rucsac.out se va afisa o singura valoare Pmax, profitul maxim care poate fi obtinut respectand conditia problemei.
Restricţii
- 1 ≤ N ≤ 5000
- 1 ≤ G ≤ 10000
- 0 ≤ Wi, Pi ≤ 10000
Exemplu
| rucsac.in | rucsac.out |
|---|---|
| 6 10 3 7 3 4 1 2 1 9 2 4 1 5 | 29 |
Explicaţie
Luam obiectele 1, 2, 4, 5 si 6, a caror greutate este 10, iar suma profiturilor este 29.
Indicatii de rezolvare
Problema rucsacului reprezinta un exemplu clasic al utilizarii programarii dinamice. Solutia pe care urmeaza a o prezenta ruleaza in timp pseudo-polinomial O(N*G), si foloseste O(N*G) memorie. O descriere mai completa a problemei si a variatelor ei este disponibila pe Wikipedia .
Vom tine un tablou bidimensional D, care va retine in celula de coordonate (i, cw) profitul maxim pe care-l putem obtine selectand o submultime a primelor i elemente, a caror greutate insumata este egala cu cw. Presupunem ca avem calculate solutiile pentru orice greutate mai mica sau egala ca G, selectand o submultime din primele i-1 elemente. Construim solutia pentru i elemente, folosindu-ne de urmatoarea recurenta: D[i][cw] = maximul dintre D[i-1][cw], situatie in care nu adaugam elementul i la solutia precedenta, si D[i-1][cw - W[i]] + P[i], cand adaugam la cea mai buna solutie cu greutatea cw - W[i] elementul i, obtinand greutatea W[i] si un profit mai mare cu P[i]. Raspunsul final se va afla in starea D[N][G]. Aceasta solutie obtine 50 de puncte.
Pentru 100 de puncte este necesar sa facem urmatoarea observatie: pentru o anumita linie din dinamica, recurenta nu se foloseste decat de linia precedenta, deci retinerea intregului tablou este inutila. In schimb, vom retine doar ultimele doua linii din matrice, reducand memoria la O(N). De asemenea putem sa reţinem tot timpul o singura linie, dacă parcurgem linia în sensul invers al greutăţilor, cum puteti observa in aceasta solutie.
Mentionez ca exista si algoritmi greedy care, desi ruleaza intr-o complexitate a timpului cu mult sub cea a solutiei prezentate, nu reusesc sa ofere rezultatul corect, ci doar sa-l aproximeze.
