dreapta|miniatura|250x250px|Exemplu de problemă a rucsacului unidimensională (cu o singură constrângere): care cutii ar trebui să fie alese pentru a maximiza cantitatea de bani în timp ce păstrează încă greutatea totală sub 15 kg? O problemă cu mai multe constrângeri ar putea lua în considerare atât greutatea cât și volumul cutiilor. (Soluție: dacă este disponibil orice număr din fiecare cutie, atunci trei cutii galbene și trei cutii gri; dacă doar cele prezentate sunt disponibile, atunci toate, mai puțin cutia verde.) Problema rucsacului este o problemă de : Dată fiind o mulțime de elemente, fiecare cu o greutate și o valoare, se determină numărul din fiecare element al mulțimii care poate fi inclus într-o colecție, astfel încât greutatea totală să fie mai mică sau egală cu o anumită limită și valoarea totală să fie cât mai mare. Ea își trage numele de la problema cu care se confruntă cineva care este obligat să umple un rucsac de dimensiune fixă cu elementele cele mai valoroase.
Problema apare adesea în unde există constrângeri financiare și este studiată în domenii cum ar fi combinatorica, informatica, teoria complexității, criptografia, matematicile aplicate și .
Problema rucsacului a fost studiată de peste un secol, primele lucrări datând de la 1897. Denumirea „problema rucsacului” datează de la începutul activității matematicianului (1884–1956),Dantzig, Tobias. Numbers: The Language of Science, 1930. și se referă la problema banală de împachetare a celor mai valoroase sau utile elemente fără a supraîncărca bagajul.
Aplicații Un studiu efectuat în 1998 la Stony Brook University Algorithm Repository a arătat că, din 75 de probleme de algoritmică, problema rucsacului fost a 18-a cea mai populară și a 4-a cea mai necesară după , , și .
Probleme ale rucsacului apar în lumea reală în procesele de luare a deciziilor într-o varietate de domenii, cum ar fi găsirea unei metode de a tăia materia primă cu risipă minimă,Kellerer, Pferschy, and Pisinger 2004, p. 449 selecția de investiții și portofolii,Kellerer, Pferschy, and Pisinger 2004, p. 461 selecția de active ,Kellerer, Pferschy, and Pisinger 2004, p. 465 și generarea de chei pentru Merkle–HellmanKellerer, Pferschy, and Pisinger 2004, p. 472 și alte .
O aplicație timpurie a problemei rucsacului a fost în construcția și notarea testelor în care cei care dau testul au de ales la care întrebări să răspundă. Pentru exemple mici, procesul este destul de simplu. De exemplu, dacă un examen conține 12 întrebări, fiecare în valoare de 10 puncte, examinații au nevoie să răspundă la doar 10 întrebări pentru a obține punctajul maxim de 100 de puncte. Cu toate acestea, pe teste cu o distribuție eterogenă a valorilor întrebărilor—de exemplu, diferite întrebări au punctaje diferite— este mult mai dificil să se facă o alegere. Feuerman și Weiss au propus un sistem în care elevii primesc un test eterogen cu un total de 125 de puncte posibile. Elevii sunt rugați să răspundă la toate întrebările după cum pot ei mai bine. Dintre posibilele submulțimi de întrebări al căror punctaj total ajunge la 100, un algoritm de problema rucsacului ar determina care submulțime oferă fiecărui elev cel mai mare scor posibil.
Definiție Cele mai frecventă problemă de rezolvat este problema rucsacului 0-1, care restricționează numărul xi de exemplare din fiecare tip de articol la zero sau unu. Având în vedere o mulțime de n elemente, numerotate de la 1 la n, fiecare cu o greutate wi și o valoare vi, împreună cu o capacitate maximă de greutate W, să se maximizeze cu constrângerea și . Aici, xi reprezintă numărul de obiecte din categoria i de inclus în rucsac. Informal, problema este de a maximiza suma valorilor elementelor din rucsac, astfel încât suma ponderilor să fie mai mică sau egală cu capacitatea rucsacului.
Problema rucsacului mărginită (BKP) elimină restricția ca fiecare element să fie luat o singură dată, dar limitează numărul de exemplare din fiecare tip de articol la o valoare maximă întreagă nenegativă : să se maximizeze cu constrângerea și Problema rucsacului nemărginită (UKP) nu pune nicio limită superioară la numărul de exemplare din fiecare tip de produs și poate fi formulată ca mai sus, cu excepția că singura restricție asupra lui este că acesta este un număr întreg nenegativ. să se maximizeze cu constrângerea și Un exemplu de problemă a rucsacului nemărginită este dat folosind figura de la începutul acestui articol cu textul „dacă este disponibil orice număr din fiecare cutie”.
Complexitatea de calcul Problema rucsacului este interesantă din perspectivă informatică pentru mai multe motive: Forma de problemă a deciziei a problemei rucsacului (Se poate obține o valoare de cel puțin V fără a depăși greutatea W?) este NP-completă, adică nu se știe niciun algoritm care să fie atât corect cât și rapid (în timp polinomial) în toate cazurile. Deși problema deciziei este NP-completă, problema optimizării este NP-hard, rezolvarea ei fiind cel puțin la fel de dificilă ca problema deciziei, și nu se cunoaște un algoritm în timp polinomial care să poată spune dacă o soluție dată este optimă (ceea ce ar însemna că nu există nicio soluție cu V mai mare, rezolvând astfel problema deciziei, care este NP-completă). Există un algoritm ce folosește . Există , care foloseste un algoritm pseudo-polinomial ca subrutină, descris mai jos. Multe cazuri care apar în practică, și „instanțe aleatoare” din unele distribuții, pot totuși să fie rezolvate exact. Există o legătură între problemele de „decizie” și cele de „optimizare” în aceea că dacă există un algoritm polinomial care rezolvă problema „deciziei”, atunci se poate găsi valoarea maximă pentru problema de optimizare în timp polinomial prin aplicarea acestui algoritm iterativ, crescând valoarea lui k . Pe de altă parte, dacă un algoritm găsește valoarea optimă a problemei de optimizare în timp polinomial, atunci problema deciziei poate fi rezolvată în timp polinomial prin compararea soluției produse la ieșire de acest algoritm cu valoarea k. Astfel, ambele versiuni ale problemei sunt de dificultate similară.
O temă în literatura de specialitate este aceea de a identifica cum arată cazurile „grele” ale problemei rucsacului,Pisinger, D. 2003. sau, văzând lucrurile altfel, de a identifica ceea ce proprietăți ale cazurilor, în practică, s-ar putea să le facă mai favorabile decât sugerează comportamentul lor NP-complet din cel mai rău caz. Obiectivul de a găsi aceste instanțe „grele” instanțe este pentru utilizarea lor în sistemele de criptografie cu chei publice, cum ar fi criptosistemul Merkle-Hellman.
Rezolvarea Sunt disponibili mai mulți algoritmi pentru rezolvarea problemei rucsacului, bazați pe abordarea cu programare dinamică, branch and boundS. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations, John Wiley and Sons, 1990 sau cu de ambele abordări.S. Martello, D. Pisinger, P. Toth, Dynamic programming and strong bounds for the 0-1 knapsack problem, Manag.
Algoritm de programare dinamică
Problema rucsacului nemărginită Dacă toate greutățile () sunt întregi nenegativi, problema rucsacului poate fi rezolvată în timp pseudo-polinomial folosind programarea dinamică. În cele ce urmează, se prezintă o soluție de programare dinamică pentru problema rucsacului nemărginită.
Pentru a simplifica lucrurile, se presupune că toate greutățile sunt strict pozitive (). Se cere maximizarea valorii totale, cu constrângerea că greutatea totală este mai mică sau egală cu . Apoi, pentru fiecare , se definește ca fiind valoarea maximă care poate fi atinsă cu greutatea totală mai mică sau egală cu . Atunci, este soluția problemei.
Se observă că are următoarele proprietăți: (suma a zero elemente, adică sumă peste mulțimea vidă)
unde este valoarea celui de al i-lea tip de element.
(Pentru a formula ecuația de mai sus, ideea folosită este ca soluția pentru un rucsac este aceeași ca valoarea unui element corect plus soluția pentru un rucsac cu capacitate mai mică, anume una cu capacitate redusă cu greutatea elementului ales.)
Aici, maximul mulțimii vide este considerată a fi zero. Tabelând rezultatele de la până la rezultă soluția. Deoarece calculul de fiecărui presupune examinarea a elemente, și există valori ale lui de calculat, timpul de rulare a soluției de programare dinamică este . Împărțirea la cel mai mare divizor comun al lor este un mod de a îmbunătăți timpul de funcționare.
Complexitatea de nu contrazice faptul că problema rucsacului este NP-completă, deoarece , spre deosebire de , nu este polinomial în lungimea de intrare a problemei. Lungimea intrării a problemei este proporțională cu numărul de biți din , adică , nu cu în sine.
Problema rucsacului 0/1 O soluție similară pe bază de programare dinamică pentru problema rucsacului 0/1 conduce, de asemenea, la un timp pseudo-polinomial. Se presupune că sunt numere întregi strict pozitive. Se definește ca fiind valoarea maximă care poate fi atinsă cu greutatea mai mică sau egală cu folosind elemente de până la (primele elemente).
Se poate defini recursiv după cum urmează:
dacă (noul element este mai mult decât actuala limită de greutate) dacă . Soluția poate fi găsită prin calculul lui . Pentru a face acest lucru în mod eficient, se poate utiliza un tabel pentru a stoca valorile anterior calculate.
Următorul pseudo-cod descrie programul dinamic: // Intrare: // Valori (stocate în tabloul v) // Greutăți (stocate în tabloul w) // Număr de elemente distincte (n) // Capacitatea rucsacului (W)
for j from 0 to W do: m[0, j] := 0
for i from 1 to n do: for j from 0 to W do: if w[i] > j then: m[i, j] := m[i-1, j] else: m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i]) Această soluție va rula, prin urmare, în timp și în spațiu >. În plus, dacă se folosește doar tabloul unidimensional pentru a stoca valorile optime curente și se parcurge acest tablou de ori, rescriind de la la de fiecare dată, vom obține același rezultat într-un spațiu .
Meet-in-the-middle Un alt algoritm pentru problema 0/1 a rucsacului, descoperit în 1974 și uneori numit „meet-in-the-middle” din cauza paralelor cu , este exponențială în numărul de elemente diferite, dar poate fi de preferat față de algoritmul PD atunci când este mare în comparație cu n. În special, dacă sunt nenegative, dar nu întregi, algoritmul de programare dinamică ar putea fi utilizat în continuare prin scalare și rotunjire (de exemplu, folosind aritmetica în virgulă fixă), dar dacă problema necesită cifre fracționare de precizie pentru a ajunge la răspunsul corect, va trebui să fie scalat cu un factor de și algoritmul PD va avea nevoie de un spațiu de și de un timp de .
intrare: o mulțime de obiecte cu greutăți și valori ieșire: cea mai mare valoare totală a unei submulțimi<div> împarte {1...n} în două mulțimi A și B, de dimensiuni aproximativ egale calculează ponderile și valorile tuturor submulțimilor din fiecare mulțime pentru fiecare submulțime a lui A se găsește o submulțime a lui B cu cea mai mare valoare, astfel încât greutatea totală să fie mai mică decât W se ține evidența celei mai mari valori combinate găsite Algoritmul ocupă un spațiu de , și implementările eficiente ale pasului 3 (de exemplu, sortarea submulțimilor lui B după greutate, eliminând submulțimile din B care cântăresc mai mult decât alte submulțimi din B de valoare mai mare sau egală, și folosind căutarea binară pentru a găsi cea mai bună combinație) duc la un timp de execuție de . Ca și în cazul atacurilor meet-in-the-middle din criptografie, acesta îmbunătățește timpul de al unui algoritm naiv de forță brută (examinarea tuturor submulțimilor lui {1...n}), cu prețul utilizării de spațiu exponențial, în loc de constant.
Algoritmi de aproximare