Problema rucsacului
Un drumeț cu o limită de greutate, un hoț cu un sac, o firmă cu un buget și o listă de proiecte: toți se confruntă cu aceeași întrebare. Ce trebuie să intre pentru a obține cea mai mare valoare fără a depăși limita? Aceasta este problema rucsacului, iar programarea dinamică o rezolvă exact atunci când greutățile sunt numere întregi de mărime moderată.
Problema
Există n obiecte, fiecare cu o greutate și o valoare, și un rucsac care suportă cel mult greutatea W. Alegeți o mulțime de obiecte a căror greutate totală este cel mult W și a căror valoare totală este cât mai mare. Fiecare obiect intră întreg sau rămâne pe dinafară, de aceea se numește problema rucsacului 0/1. Cu n obiecte există 2ⁿ mulțimi posibile, așa că încercarea tuturor devine repede imposibilă.
Tabelul
Fie best[i][w] cea mai mare valoare care încape în greutatea w folosind doar primele i obiecte. Atunci best[0][w] = 0, iar pentru fiecare rând următor există două variante: obiectul i rămâne pe dinafară, ceea ce dă best[i − 1][w], sau, dacă greutatea lui wᵢ încape, intră în rucsac, ceea ce dă valoarea lui plus best[i − 1][w − wᵢ]. Cea mai mare dintre ele este best[i][w]. Dacă tabelul se completează rând cu rând, ambele celule necesare sunt mereu gata.
Un exemplu
Luați o capacitate de 7 și patru obiecte cu greutățile 1, 3, 4 și 5 și valorile 1, 4, 5 și 7. Doar cu primul obiect, fiecare capacitate de la 1 în sus valorează 1. Adăugând al doilea, capacitatea 4 le poate cuprinde pe amândouă, pentru 5. Adăugând al treilea, capacitatea 7 poate cuprinde obiectele 2 și 3, pentru 9. Al patrulea obiect, cu greutatea 5 și valoarea 7, s-ar putea alătura obiectului 1 pentru 8 la capacitatea 6 sau 7, dar 9 este mai bine, așa că celula din dreapta jos este 9: puneți în rucsac obiectele cu greutățile 3 și 4.
Cât de grea este?
Tabelul are nevoie de aproximativ n·W pași. Pare rapid, dar W este un număr, iar un număr cu d cifre poate fi la fel de mare ca 10 la puterea d, așa că munca crește exponențial cu lungimea datelor de intrare. Problema rucsacului este NP-dificilă; a fost una dintre cele 21 de probleme NP-complete prezentate de Richard Karp în 1972. În practică, tabelul, metoda branch and bound și schemele bune de aproximare rezolvă bine instanțe reale mari.
Istorie și aplicații
Numele provine de la matematicianul Tobias Dantzig, la începutul secolului XX, iar fiul său, George Dantzig, a dat o metodă greedy clasică pentru ea în 1957. Problemele de tip rucsac apar la întocmirea bugetelor și la alegerea portofoliilor, la tăierea materiei prime cu cât mai puține deșeuri, la încărcarea mărfurilor și chiar în criptografia timpurie cu cheie publică: criptosistemul Merkle–Hellman din 1978 se baza pe o problemă a rucsacului și a fost spart câțiva ani mai târziu.
Explorați
Deschideți aplicația, treceți la vizualizarea Tabel și apăsați Pas. Celula portocalie este cea care se completează, iar celulele albastre sunt cele două pe care le compară: celula chiar de deasupra și, în rândul de deasupra, celula aflată cu atâtea coloane mai la stânga cât cântărește obiectul. După ultima celulă, reconstituirea urcă cu portocaliu din colțul din dreapta jos, iar obiectele din rucsac apar sub tabel.
Întrebări frecvente
Care este diferența dintre problema rucsacului 0/1, mărginită și nemărginită?
În varianta 0/1, fiecare obiect este luat cel mult o dată. În varianta mărginită, fiecare obiect are un număr limitat de exemplare, iar în cea nemărginită, oricâte. Tabelul se schimbă foarte puțin de la una la alta.
Este metoda greedy vreodată corectă pentru problema rucsacului?
Pentru problema fracționară a rucsacului, în care obiectele pot fi împărțite, este optim să luați întâi cea mai bună valoare pe unitatea de greutate. Pentru obiecte întregi poate fi departe de optim, deși cea mai bună dintre soluția greedy și cel mai valoros obiect luat singur valorează întotdeauna cel puțin jumătate din cea mai bună valoare.
De câtă memorie are nevoie tabelul?
(n + 1)·(W + 1) celule pentru tabelul complet, de care aveți nevoie pentru a reconstitui obiectele. Dacă vă interesează doar cea mai bună valoare, ajunge un singur rând de W + 1 celule, completat de la dreapta la stânga.
Este problema rucsacului același lucru cu problema sumei submulțimii?
Problema sumei submulțimii este cazul particular în care valoarea fiecărui obiect este egală cu greutatea lui, iar întrebarea este dacă rucsacul poate fi umplut exact. Și ea este NP-completă și se rezolvă cu același tip de tabel.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Încercați problema rucsacului