Utilizarea si programarea calculatoarelor 2 - Laborator 12

Problema rucsacului

Se dă o mulţime de obiecte, fiecare caracterizat prin dimensiune şi valoare (numere reale), şi un rucsac cu o dimensiune totală dată. Să se aleagă o mulţime de obiecte de valoare maximă care să încapă în rucsac.

Programul va citi de la intrare întâi dimensiunea rucsacului, numărul de obiecte, şi apoi perechi cu dimensiunea şi valoarea obiectelor.

Indicaţii de rezolvare

Efectuaţi o căutare recursivă în care încercaţi pentru fiecare obiect atât o soluţie în care este ales, cât şi o soluţie în care nu este ales, şi continuaţi recursiv procedeul pentru obiectul următor. Consideraţi următoarele aspecte:

e necesară o structură de date în care să se reţină starea fiecărui obiect (ales sau nu), actualizată în timpul apelului recursiv
fiind vorba de o problemă de maxim, soluţia optimă nu va fi cunoscută decât după ce am examinat toate soluţiile fezabile (sau eventual putem afirma cu certitudine că niciuna din soluţiile neexaminate nu poate fi mai bună decât cea găsită). E necesară deci o variabilă în care se ţine minte soluţia cea mai bună găsită până în prezent, şi care e actualizată când se găseşte una mai bună.
în apelul recursiv trebuie actualizate valoarea curentă, locul rămas disponibil în rucsac, şi starea obiectului curent (ales sau nu), inclusiv la revenirea din apel.

Observaţii pentru studiu suplimentar (facultativ)

În formularea dată, cu dimensiuni numere reale, problema necesită în general un număr de încercări exponenţial în numărul de obiecte. O abordare greedy care alege întâi obiectul cu valoare relativă maximă (raportată la dimensiune) nu conduce în mod necesar la soluţia optimă.

Totuşi, sortarea obiectelor după valoare relativă şi folosirea celor mai bune întâi în procedura recursivă poate fi uneori o euristică bună.

Se poate reţine pe parcurs o estimare optimistă (limită superioară) pentru valoarea maximă cu care ar putea creşte soluţia curentă dacă rucsacul s-ar umple complet (dimensiunea rămasă înmulţită cu valoarea relativă a celui mai bun obiect neales), şi se poate renunţa la căutarea pe ramura curentă dacă această limită superioară e mai mică decât cea mai bună soluţie găsită deja (o tehnică denumită branch and bound).

În varianta cu dimensiuni numere întregi, problema admite o rezolvare diferită, mai eficientă. Se completează un tabel cu două dimensiuni: numărul de obiecte şi dimensiunea întreagă a rucsacului, în care t[k][D] reţine valoarea maximă ce se poate obţine pentru dimensiunea D cu obiectele 1..k. Se poate stabili atunci relaţia recursivă: t[k+1][D] = max(t[k][D] + t[k][D-d[k+1]]) (soluţia fie va nu include obiectul k+1, fie îl va include, în ambele cazuri restul spaţiului trebuie umplut optim cu obiecte până la k. Tabelul se poate completa pornind de la k = 1 la numărul de obiecte, procedeul general fiind numit programare dinamică.

Marius Minea

Last modified: Sun May 16 17:39:04 EEST 2004