Problema rucsacului

Problema rucsacului este o problemă de optimizare combinatorică^⁠(d): 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.

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 apare adesea în alocarea resurselor^⁠(d) unde există constrângeri financiare și este studiată în domenii cum ar fi combinatorica, informatica, teoria complexității, criptografia, matematicile aplicate și jocurile cu echipe sportive imaginare^⁠(d).

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 Tobias Dantzig^⁠(d) (1884–1956), ș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ă arborii kd^⁠(d), arborii de sufixe^⁠(d), și problema bin packing^⁠(d).

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ă, selecția de investiții și portofolii, selecția de active titrizarea garantată cu active^⁠(d), și generarea de chei pentru Merkle–Hellman și alte criptosisteme bazate pe problema rucsacului^⁠(d).

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 x_i 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 w_i și o valoare v_i, împreună cu o capacitate maximă de greutate W,

să se maximizeze $\sum _{i=1}^{n}v_{i}x_{i}$

cu constrângerea $\sum _{i=1}^{n}w_{i}x_{i}\leq W$ și $x_{i}\in \{0,1\}$.

Aici, x_i 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 ${\displaystyle }$ de exemplare din fiecare tip de articol la o valoare maximă întreagă nenegativă ${\displaystyle }$:

să se maximizeze $\sum _{i=1}^{n}v_{i}x_{i}$

cu constrângerea $\sum _{i=1}^{n}w_{i}x_{i}\leq W$ și $0\leq x_{i}\leq c$

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 ${\displaystyle }$ este că acesta este un număr întreg nenegativ.

să se maximizeze $\sum _{i=1}^{n}v_{i}x_{i}$

cu constrângerea $\sum _{i=1}^{n}w_{i}x_{i}\leq W$ și $x_{i}\geq 0$

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^⁠(d) 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 în timp pseudo-polinomial^⁠(d) ce folosește programarea dinamică^⁠(d).
• Există  schemă de aproximare complet în timp polinomial^⁠(d), 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, 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 bound sau cu hibridizări^⁠(d) de ambele abordări.

Algoritm de programare dinamică

Problema rucsacului nemărginită

Dacă toate greutățile ($w_{1},\ldots ,w_{n}$) 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 ($w_{i}>0$). Se cere maximizarea valorii totale, cu constrângerea că greutatea totală este mai mică sau egală cu W. Apoi, pentru fiecare $w\leq W$, se definește $m[w]$ ca fiind valoarea maximă care poate fi atinsă cu greutatea totală mai mică sau egală cu w. Atunci, $m[W]$ este soluția problemei.

Se observă că $m[w]$ are următoarele proprietăți:

• $m[0]=0\,\!$ (suma a zero elemente, adică sumă peste mulțimea vidă)
• $m[w]=\max _{w_{i}\leq w}(v_{i}+m[w-w_{i}])$

unde $v_{i}$ 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 $m[0]$ până la $m[W]$ rezultă soluția. Deoarece calculul de fiecărui $m[w]$ presupune examinarea a n elemente, și există W valori ale lui $m[w]$ de calculat, timpul de rulare a soluției de programare dinamică este $O(nW)$. Împărțirea $w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W$ la cel mai mare divizor comun al lor este un mod de a îmbunătăți timpul de funcționare.

Complexitatea de $O(nW)$ nu contrazice faptul că problema rucsacului este NP-completă, deoarece W, spre deosebire de n, nu este polinomial în lungimea de intrare a problemei. Lungimea intrării W a problemei este proporțională cu numărul de biți din W, adică $\log W$, nu cu W î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ă $w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W$ sunt numere întregi strict pozitive. Se definește $m[i,w]$ ca fiind valoarea maximă care poate fi atinsă cu greutatea mai mică sau egală cu $w$ folosind elemente de până la i (primele i elemente).

Se poate defini $m[i,w]$ recursiv după cum urmează:

• $m[0,\,w]=0$
• $m[i,\,w]=m[i-1,\,w]$ dacă $w_{i}>w\,\!$ (noul element este mai mult decât actuala limită de greutate)
• $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ dacă $w_{i}\leqslant w$.

Soluția poate fi găsită prin calculul lui $m[n,W]$. 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 $O(nW)$ și în spațiu $O(nW)$>. În plus, dacă se folosește doar tabloul unidimensional $m[w]$ pentru a stoca valorile optime curente și se parcurge acest tablou de $i+1$ ori, rescriind de la $m[W]$ la $m[1]$ de fiecare dată, vom obține același rezultat într-un spațiu $O(W)$.

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 un algoritm cu nume similar din criptografie^⁠(d), este exponențială în numărul de elemente diferite, dar poate fi de preferat față de algoritmul PD atunci când W este mare în comparație cu n. În special, dacă $w_{i}$ sunt nenegative, dar nu întregi, algoritmul de programare dinamică ar putea fi utilizat în continuare prin scalare și rotunjire^⁠(d) (de exemplu, folosind aritmetica în virgulă fixă), dar dacă problema necesită d cifre fracționare de precizie pentru a ajunge la răspunsul corect, W va trebui să fie scalat cu un factor de $10^{d}$ și algoritmul PD va avea nevoie de un spațiu de $O(W10^{d})$ și de un timp de $O(nW10^{d})$.

  intrare:
    o mulțime de obiecte cu greutăți și valori
  ieșire:

cea mai mare valoare totală a unei submulțimi

î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 $O(2^{n/2})$, ș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 $O(n2^{n/2})$. Ca și în cazul atacurilor meet-in-the-middle din criptografie, acesta îmbunătățește timpul de $O(n*2^{n})$ 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

Ca și pentru majoritatea problemelor NP-complete, s-ar putea să fie suficient să se găsească soluții viabile, chiar dacă acestea nu sunt optime. De preferință, însă, aproximarea vine cu o garanție cu privire la diferența dintre valoarea soluției găsită și valoarea soluției optime.

Ca și în mulți algoritmi utili dar complecși computațional, s-au făcut cercetări substanțiale privind crearea și analiza algoritmilor care aproximează o soluție. Problema rucsacului, deși NP-hard, este una dintr-o colecție de algoritmi care încă pot fi aproximați până la orice grad specificat. Aceasta înseamnă că problema are o schemă de aproximare în timp polinomial. Mai exact, problema rucsacului are o schemă de aproximare în timp polinomial complet (FPTAS).

Algoritm de aproximare greedy

George Dantzig a propus un algoritm greedy de aproximare^⁠(d) pentru a rezolva problema rucsacului nemărginită. Versiunea lui sortează elementele în ordinea descrescătoare a valorii pe unitatea de greutate, $v_{i}/w_{i}$. Se trece apoi la introducerea în sac, începând cu un număr cât mai mare de exemplare din primul tip de element până când nu mai este spațiu în rucsac pentru mai multe. Dat fiind că există număr nelimitat din fiecare tip de element, dacă ${\displaystyle }$ este valoarea maximă de elemente care se încadrează în sac, atunci algoritmul greedy este garantat să obțină cel puțin o valoare de $m/2$. Cu toate acestea, pentru problema mărginită, unde rezerva din fiecare tip de element este limitată, algoritmul poate fi departe de optim.

Schema de aproximare în timp polinomial complet

Schema de aproximare în timp polinomial complet^⁠(d) (FPTAS) pentru problema rucsacului profită de faptul că motivul pentru care problema nu are soluții în timp polinomial este că profiturile asociate cu elementele nu sunt restricționate. Dacă se rotunjesc unele din cele mai puțin semnificative cifre ale valorilor de profit, atunci ele vor fi mărginite de un polinom și 1/ε unde ε este o limită a corectitudinii soluției. Această restricție înseamnă că un algoritm poate găsi în timp polinomial o soluție corectă într-un factor de (1-ε) de soluția optimă.

 intrare: 
   ε ∈ (0,1]
   o listă de n elemente, specificată prin valorile lor, $v_{i}$ și greutățile
 ieșire:
   S', soluția FPTAS

 P := max ${\displaystyle }$ // cea mai mare valoare
 K := ε ${\displaystyle }$
 for i from 1 to n do
     $v'_{i}$ := $\left\lfloor {\frac {v_{i}}{K}}\right\rfloor$
 end for
 return soluția, S', folosind valorile $v'_{i}$ din programul dinamic prezentat mai sus

Teoremă: mulțimea $S'$ calculată prin algoritmul de mai sus îndeplinește $\mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})$, unde $S^{*}$ este o soluție optimă.

Relații de dominanță

Rezolvarea problemei rucsacului nemărginite poate fi făcută mai ușor eliminând obiecte care nu vor fi niciodată incluse. Fie un element dat i, cu condiția că am putea găsi o mulțime de elemente J astfel încât greutatea lor totală să fie mai mică decât greutatea lui i, iar valoarea lor totală este mai mare decât valoarea lui i. Atunci i nu va apărea în soluția optimă, pentru că întotdeauna s-ar putea îmbunătăți orice potențială soluție conținând i prin înlocuirea lui i cu mulțimea J. Prin urmare, se poate ignora al i-lea element cu totul. În astfel de cazuri, se spune că J îl domină pe i. (Acesta nu se aplică la problemele mărginite, deoarece în acel caz obiectele din J s-ar putea să fi fost deja folosite.)

Găsirea relațiilor de dominanță permite reducerea semnificativă a dimensiunii spațiului de căutare. Există mai multe tipuri diferite de relații de dominanțăr, toate satisfăcând o inegalitate de forma:

$\qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}$ și $\sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,$ pentru un $x\in Z_{+}^{n}$

unde $\alpha \in Z_{+}\,,J\subsetneq N$ și $i\not \in J$. Vectorul x reprezintă numărul de copii ale fiecărui membru al lui J.

Dominanță colectivă

Al i-lea element este dominat colectiv de J, relație scrisă $i\ll J$, dacă greutatea totală a unei combinații de elemente din J este mai mică decât w_i și valoarea lor totală este mai mare decât v_i. Formal, $\sum _{j\in J}w_{j}\,x_{j}\ \leq w_{i}$ și $\sum _{j\in J}v_{j}\,x_{j}\ \geq v_{i}$ pentru un $x\in Z_{+}^{n}$, adică $\alpha =1$. Verificarea acestei dominanțe este dificilă din punct de vedere computațional, așa că nu poate fi utilizată cu o abordare de programare dinamică. De fapt, aceasta este echivalentă cu rezolvarea unei probleme a rucsacului, în forma de decizie, mai mici unde $V=v_{i}$, $W=w_{i}$, și elementele sunt restricționate la J.

Dominanța cu prag

Al i-lea element este dominat cu prag de J, relație scrisă ca $i\prec \prec J$, dacă un număr de copii ale lui $i$ sunt dominate de J. Formal, $\sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}$, și $\sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,$ pentru un $x\in Z_{+}^{n}$ și $\alpha \geq 1$. Este o generalizare a dominanței colective, introdusă pentru prima oară în și utilizată în algoritmul EDUK. Cel mai mic astfel de $\alpha$ definește pragul elementului $i$, relație scrisă $t_{i}=(\alpha -1)w_{i}$. În acest caz, soluția optimă ar putea conține cel mult $\alpha -1$ copii ale lui $i$.

Dominanța multiplă

Al i-lea element este multiplu dominat de un singur element $j$, relație scrisă ca $i\ll _{m}j$, dacă $i$ este dominat de un număr de copii ale lui $j$. Formal, $w_{j}\,x_{j}\ \leq w_{i}$, și $v_{j}\,x_{j}\ \geq v_{i}$ pentru un $x_{j}\in Z_{+}$ adică $J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor$. Această dominanță poate fi utilizată eficient în preprocesare deoarece poate fi detectată relativ ușor.

Dominanță modulară

Fie b cel mai bun element, adică ${\frac {v_{b}}{w_{b}}}\geq {\frac {v_{i}}{w_{i}}}\,$ pentru orice $i$. Acesta este elementul cu cea mai mare densitate de valoare. Al i-lea element este modular dominat de un singur element $j$, relație scrisă ca $i\ll _{\equiv }j$, dacă $i$ este dominat de $j$ plus mai multe copii ale lui b. Formal, $w_{j}+tw_{b}\leq w_{i}$, și  $v_{j}+tv_{b}\geq v_{i}$ adică $J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1$.

Variații

Există mai multe variații ale problemei rucsacului, apărute din numărul mare de aplicații ale problemei de bază. Principalele variații apar prin schimbarea numărului unui parametru al problemei, cum ar fi numărul de elemente, numărul de obiective, sau chiar numărul de rucsacuri.

Problema rucsacului multiobiectiv

Această variație modifică obiectivul individual al umplerii rucsacului. În loc de un singur obiectiv, cum ar fi maximizarea profitului monetar, obiectivul ar putea avea mai multe dimensiuni. De exemplu, ar putea fi obiective de mediu, sociale, și economice. Probleme frecvent abordate includ optimizările portofoliilor și ale logisticii de transport.

Ca exemplu concret, se presupune gestiunea unui vas de croazieră. Trebuie să se decidă câți actori de comedie să se angajeze. Acest nu poate ocupa mai mult de o tonă de pasageri și actorii trebuie să cântărească mai puțin de 1000 kg. Fiecare actor are o greutate, aduce o valoare de business în funcție de popularitatea sa și cere un anumit salariu. În acest exemplu sunt mai multe obiective. Se dorește, desigur, maximizarea popularității actorilor și minimizarea salariului. De asemenea, se dorește un număr cât mai mare de actori.

Problema rucsacului multidimensională

În această variantă, greutatea elementului i este dată de un vector D-dimensional ${\overline {w_{i}}}=(w_{i1},\ldots ,w_{iD})$ și rucsacul are un vector de capacități D-dimensional $(W_{1},\ldots ,W_{D})$. Obiectivul este de a maximiza suma valorilor elementelor în rucsac, astfel încât suma greutăților pe fiecare dimensiune d să nu depășească $W_{d}$.

Calculul problemei multi-dimensionale a rucsacului este mai greu decât cel al problemei simple; chiar și pentru $D=2$ problema nu are nici măcar schemă de aproximare în timp polinomial^⁠(d) decât dacă P$=$NP. Cu toate acestea, algoritmul din Cohen & Grebla 2014. este demonstrat a rezolva eficient cazurile rare. Un exemplu de problemă multi-dimensională a rucsacului este rară dacă există o mulțime $J=\{1,2,\ldots ,m\}$ pentru $m<D$ astfel încât pentru fiecare element i, $\exists z>m$ astfel încât $\forall j\in J\cup \{z\},\ w_{ij}\geq 0$ și $\forall y\notin J\cup \{z\},w_{iy}=0$. Astfel de situații apar, de exemplu, atunci când se planifică pachetele într-o rețea fără fir cu noduri de retransmisie. Algoritmul din  rezolvă și el cazurile rare ale variantei cu alegere multiplă.

Algoritmul IHS (Increasing Height Shelf) este optim pentru problema rucsacului 2D (acoperirea cu pătrate a unui pătrat unitar bidimensional): atunci când există cel mult cinci pătrate într-o acoperire optimă.

Problema rucsacurilor multiple

Această variație este similară cu problema bin packing^⁠(d), dar diferă de aceasta prin aceea că se poate alege o submulțime de elemente, pe când, în problema bin packing, toate produsele trebuie să fie ambalate în anumite compartimente. Conceptul este că există mai multe rucsacuri. Această schimbare ar părea banală, dar nu este echivalentă cu adăugarea la capacitatea inițială. Această variație este folosită în multe probleme de încărcare și planificare din cercetarea operațională și are schemă de aproximare în timp polinomial.

Problema rucsacului pătratică

Așa cum este descrisă de către Wu et al.:

Problema problema pătratică (QKP) maximizează o funcție obiectiv pătratică supusă unei constrângeri binare și liniare de capacitate.

Problema rucsacului pătratică fost discutată sub acest titlu de Gallo, Hammer și Simeone în 1980. Gallo și Simeone pun însă prima tratare a problemei pe seama lui Witzgall în 1975.

Problema sumei submulțimilor

Problema sumei submulțimilor este un caz special al problemelor de decizie și 0-1 în care pentru fiecare tip de element, greutatea este egală cu valoarea: $w_{i}=v_{i}$. În domeniul criptografiei, termenul problema rucsacului este adesea folosit pentru a se referi în mod special la problema sumei submulțimilor și este cunoscută ca fiind una dintre cele 21 de probleme NP-complete ale lui Karp.

Generalizarea problemei sumei submulțimilor se numește problema sumei submulțimilor multiplă, în care există mai multe compartimente cu aceeași capacitate. S-a demonstrat că generalizarea nu are schemă de aproximare în timp polinomial.

În cultura populară

• Neal Stephenson dă un exemplu de problema rucsacului în capitolul 70 din romanul său, Cryptonomicon^⁠(d), pentru a distribui obiecte memoriale din familie.
• Problema rucsacului apare de obicei în jocuri de rol, atât digitale cât și pe hârtie (exemple proeminente includ seria The Elder Scrolls și, respectiv, jocul Dungeons and Dragons), unde personajul jucătorului este constrâns de pragul lor de cuprindere atunci când transportă obiecte și comori, ceea ce obligă regulat jucătorul să evalueze obiectele după raportul valoare-greutate, pentru a duce doar elementele dense valoric unui negustor.
• Problema rucsacului face obiectul glumei din Web-comicul xkcd #287 intitulat "NP-Complete"

Note

Bibliografie

• Garey, Michael R.; David S. Johnson^⁠(d) (1979). Computers and Intractability^⁠(d). W.H. Freeman. ISBN 0-7167-1045-5.  A6: MP9, pg.247.
• Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Knapsack Problems. Springer. doi:10.1007/978-3-540-24777-7. ISBN 3-540-40286-1. 
• Martello, Silvano; Toth, Paolo (1990). Knapsack problems: Algorithms and computer implementations. Wiley-Interscience. ISBN 0-471-92420-2. 

Legături externe

• Descărcare gratuită a cărții „Probleme ale rucsacului: algoritmi si implementări pe calculator”, de Silvano Martello și Paolo Toth Arhivat în 6 mai 2017, la Wayback Machine.
• Slide-uri de curs pe problema rucsacului
• PYAsUKP: Yet Another solver for the Unbounded Knapsack Problem Arhivat în 6 octombrie 2011, la Wayback Machine., cu cod ce profită de relațiile de dominanță într-un algoritm hibrid,  teste de referință și copii descărcabile ale unor articole.
• Pagina de start a lui David Pisinger cu copii descărcabile ale unor articole din lista de publicații (inclusiv "Unde sunt problemele grele ale rucsacului?")
• Soluții la problema rucsacului în mai multe limbi la Rosetta Code^⁠(d)
• Algoritm de programare dinamică pentru problema rucsacului 0/1
• Site care rezolvă on-line problema rucsacului Arhivat în 23 februarie 2014, la Wayback Machine.
• Rezolvarea 0-1-RUCSAC cu algoritmi genetici în Ruby Arhivat în 23 mai 2011, la Wayback Machine.
• Coduri pentru problema rucsacului pătratică Arhivat în 14 februarie 2015, la Wayback Machine.