Fişierul intrare/ieşire:rucsac.in, rucsac.outSursăArhiva Educationala
AutorArhiva EducationalaAdăugată deGavrilaVladGavrila Vlad GavrilaVlad
Timp execuţie pe test0.4 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/A

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.inrucsac.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.

Probleme propuse:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content