Vizualizare sursă pentru „Problema rucsacului”

[[Fișier:Knapsack.svg|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&nbsp;kg? O problemă cu mai multe constrângeri ar putea lua în considerare atât greutatea cât și volumul cutiilor. <br>
(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 {{Ill-wd|Q1333872|3=optimizare combinatorică}}: 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 {{Ill-wd|Q287260|3=alocarea resurselor}} unde există constrângeri financiare și este studiată în domenii cum ar fi [[Combinatorică|combinatorica]], [[Informatică|informatica]], [[teoria complexității]], [[Criptografie|criptografia]], [[Matematică aplicată|matematicile aplicate]] și {{Ill-wd|Q5209256|3=jocurile cu echipe sportive imaginare}}.

Problema rucsacului a fost studiată de peste un secol, primele lucrări datând de la 1897.<ref>{{cite journal|title=On the partition of numbers|author=Mathews, G. B.|journal=Proceedings of the London Mathematical Society|volume=28|pages=486&ndash;490|date=25 June 1897|url=http://plms.oxfordjournals.org/content/s1-28/1/486.full.pdf|doi=10.1112/plms/s1-28.1.486}}</ref> Denumirea „problema rucsacului” datează de la începutul activității matematicianului {{Ill-wd|Q3290663}} (1884&#x2013;1956),<ref>Dantzig, Tobias. Numbers: The Language of Science, 1930.</ref> și se referă la [[probleme de împachetare |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 [http://www.cs.sunysb.edu/~algorith/ 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ă {{Ill-wd|Q309949|3=arborii kd}}, {{Ill-wd|Q1426863|3=arborii de sufixe}}, și {{Ill-wd|Q814581|3=problema bin packing}}.<ref>{{cite journal|title=Who is Interested in Algorithms and Why? Lessons from the Stony Brook Algorithm Repository|author=Skiena, S. S.|journal=AGM SIGACT News|volume=30|issue=3|date=September 1999|pages=65&ndash;74|ISSN=0163-5700|url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41.8357&rep=rep1&type=pdf|archive-url=https://web.archive.org/web/20160306144224/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41.8357&rep=rep1&type=pdf|dead-url=yes|archive-date=2016-03-06|doi=10.1145/333623.333627}}</ref>

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ă,<ref>Kellerer, Pferschy, and Pisinger 2004, p. 449</ref> selecția de investiții și portofolii,<ref>Kellerer, Pferschy, and Pisinger 2004, p. 461</ref> selecția de active {{Ill-wd|Q852175|3=titrizarea garantată cu active}},<ref>Kellerer, Pferschy, and Pisinger 2004, p. 465</ref> și generarea de chei pentru [[Merkle-Hellman|Merkle–Hellman]]<ref>Kellerer, Pferschy, and Pisinger 2004, p. 472</ref> și alte {{Ill-wd|Q18343476|3=criptosisteme bazate pe problema rucsacului}}.

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&#x2014;de exemplu, diferite întrebări au punctaje diferite&#x2014; 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.<ref>{{cite journal|title=A Mathematical Programming Model for Test Construction and Scoring|journal=Management Science|volume=19|issue=8|date=April 1973|pages=961–966|author1=Feuerman, Martin|author2=Weiss, Harvey|jstor=2629127|doi=10.1287/mnsc.19.8.961}}</ref>

== Definiție ==
Cele mai frecventă problemă de rezolvat este '''problema rucsacului 0-1''', care restricționează numărul ''x<sub>i</sub>'' 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<sub>i</sub>'' și o valoare ''v<sub>i</sub>'', împreună cu o capacitate maximă de greutate ''W'',
: să se maximizeze <math>\sum_{i=1}^n v_i x_i</math>
: cu constrângerea <math>\sum_{i=1}^n w_i x_i \leq W</math> și <math>x_i \in \{0,1\}</math>.
Aici, ''x<sub>i</sub>'' 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 <math /> de exemplare din fiecare tip de articol la o valoare maximă întreagă nenegativă <math />:
: să se maximizeze <math>\sum_{i=1}^n v_i x_i</math>
: cu constrângerea <math>\sum_{i=1}^n w_i x_i \leq W</math> și <math>0 \leq x_i \leq c</math>
'''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 <math /> este că acesta este un [[număr întreg]] nenegativ.
: să se maximizeze <math>\sum_{i=1}^n v_i x_i</math>
: cu constrângerea <math>\sum_{i=1}^n w_i x_i \leq W</math> și <math>x_i \geq 0</math>
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 {{Ill-wd|Q3262192|3=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-completitudine|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 {{Ill-wd|Q155291|3=în timp pseudo-polinomial}} ce folosește {{Ill-wd|Q380679|3=programarea dinamică}}.
* Există  {{Ill-wd|Q843550|3=schemă de aproximare complet în timp polinomial}}, 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,<ref name="pisinger200308">Pisinger, D. 2003. </ref><ref name="Cacetta2001">{{cite journal|last1=Caccetta|first1=L.|last2=Kulanoot|first2=A.|year=2001|title=Computational Aspects of Hard Knapsack Problems|url=|journal=Nonlinear Analysis|volume=47|issue=|pages=5547–5558|doi=10.1016/s0362-546x(01)00658-7}}</ref> 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.<ref name="poirriez_et_all_2009">{{cite journal|last1=Poirriez|first1=Vincent|last2=Yanev|first2=Nicola|last3=Andonov|first3=Rumen|title=A hybrid algorithm for the unbounded knapsack problem|journal=Discrete Optimization|volume=6|issue=1|year=2009|pages=110–124|issn=1572-5286|doi=10.1016/j.disopt.2008.09.004}}</ref> Obiectivul de a găsi aceste instanțe „grele” instanțe este pentru utilizarea lor în sistemele de [[Criptografie asimetrică|criptografie cu chei publice]], cum ar fi [[Merkle-Hellman|criptosistemul Merkle-Hellman]].

== Rezolvarea ==
Sunt disponibili mai mulți algoritmi pentru rezolvarea problemei  rucsacului, bazați pe abordarea cu programare dinamică,<ref name="eduk2000">{{cite journal|last1=Andonov|first1=Rumen|last2=Poirriez|first2=Vincent|last3=Rajopadhye|first3=Sanjay|year=2000|title=Unbounded Knapsack Problem : dynamic programming revisited|url=|journal=European Journal of Operational Research|volume=123|issue=2|pages=168–181|doi=10.1016/S0377-2217(99)00265-9}}</ref> branch and bound<ref name="martellototh90">S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations,
John Wiley and Sons, 1990</ref> sau cu {{Ill-wd|Q17092099|3=hibridizări}} de ambele abordări.<ref name="martellopisingertoth99a">S. Martello, D. Pisinger, P. Toth, Dynamic programming and strong bounds for the 0-1 knapsack problem, ''Manag. ''</ref><ref name="plateau85">{{cite journal|last1=Plateau|first1=G.|last2=Elkihel|first2=M.|year=1985|title=A hybrid algorithm for the 0-1 knapsack problem|url=|journal=Methods of Oper. Res.|volume=49|issue=|pages=277–293}}</ref><ref name="martellotothe99">{{cite journal|last1=Martello|first1=S.|last2=Toth|first2=P.|year=|title=A mixture of dynamic programming and branch-and-bound for the subset-sum problem|url=|journal=Manag. Sci.|volume=30|issue=|pages=765–771|doi=10.1287/mnsc.30.6.765}}</ref>

=== Algoritm de programare dinamică ===

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

Se observă că <math>m[w]</math> are următoarele proprietăți:
* <math>m[0]=0\,\!</math> (suma a zero elemente, adică sumă peste mulțimea vidă)
* <math>m[w]= \max_{w_i \le w}(v_i+m[w-w_i])</math>
unde <math>v_i</math> 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 <math>m[0]</math> până la <math>m[W]</math> rezultă soluția. Deoarece calculul de fiecărui <math>m[w]</math> presupune examinarea a {{math|n}} elemente, și există {{math|W}} valori ale lui <math>m[w]</math> de calculat, timpul de rulare a soluției de programare dinamică este <math>O(nW)</math>. Împărțirea <math>w_1,\,w_2,\,\ldots,\,w_n,\,W</math> la [[cel mai mare divizor comun]] al lor este un mod de a îmbunătăți timpul de funcționare.

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

Se poate defini <math>m[i,w]</math> recursiv după cum urmează:
* <math>m[0,\,w]=0</math>
* <math>m[i,\,w]=m[i-1,\,w]</math> dacă <math>w_i > w\,\!</math> (noul element este mai mult decât actuala limită de greutate)
* <math>m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_i]+v_i)</math> dacă <math>w_i \leqslant w</math>.
Soluția poate fi găsită prin calculul lui <math>m[n,W]</math>. 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:
<source lang="c" line>
// 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])

</source>
Această soluție va rula, prin urmare, în timp <math>O(nW)</math> și în spațiu <math>O(nW)</math>>. În plus, dacă se folosește doar tabloul unidimensional <math>m[w]</math> pentru a stoca valorile optime curente și se parcurge acest tablou de <math>i+1</math> ori, rescriind de la <math>m[W]</math> la <math>m[1]</math> de fiecare dată, vom obține același rezultat într-un spațiu <math>O(W)</math>.

=== Meet-in-the-middle ===
Un alt algoritm pentru problema 0/1 a rucsacului, descoperit în 1974 <ref>{{Citation|title=Computing partitions with applications to the knapsack problem|year=1974|last1=Horowitz|last2=Sahni|first1=Ellis|first2=Sartaj|author2-link=Sartaj Sahni|journal=Journal of the Association for Computing Machinery|volume=21|pages=277–292|doi=10.1145/321812.321823}}</ref> și uneori numit „meet-in-the-middle” din cauza paralelor cu {{Ill-wd|Q938066|3=un algoritm cu nume similar din criptografie}}, este exponențială în numărul de elemente diferite, dar poate fi de preferat față de algoritmul PD atunci când {{math|W}} este mare în comparație cu n. În special, dacă <math>w_i</math> sunt nenegative, dar nu întregi, algoritmul de programare dinamică ar putea fi utilizat în continuare prin [[scalare (geometrie)|scalare]] și {{ill-wd|Q663208}} (de exemplu, folosind [[Virgulă fixă|aritmetica în virgulă fixă]]), dar dacă problema necesită {{math|d}} cifre fracționare de precizie pentru a ajunge la răspunsul corect, {{math|W}} va trebui să fie scalat cu un factor de <math>10^d</math> și algoritmul PD va avea nevoie de un spațiu de <math>O(W10^d)</math> și de un timp de <math>O(nW10^d)</math>.

   '''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 <math>O(2^{n/2})</math>, ș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ăutare binară|căutarea binară]] pentru a găsi cea mai bună combinație) duc la un timp de execuție de <math>O(n2^{n/2})</math>. Ca și în cazul atacurilor meet-in-the-middle din criptografie, acesta îmbunătățește timpul de <math>O(n*2^n)</math> 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).<ref name="Vazirani, Vijay 2003">Vazirani, Vijay. Approximation Algorithms. Springer-Verlag Berlin Heidelberg, 2003.</ref>

==== Algoritm de aproximare greedy ====
[[George Dantzig]] a propus un {{Ill-wd|Q621751|3=algoritm greedy de aproximare}} pentru a rezolva problema rucsacului nemărginită.<ref name="dantzig1957">{{Citat revistă|nume=Dantzig|prenume=George B.|legătură-autor=George Dantzig|an=1957|titlu=Discrete-Variable Extremum Problems|journal=Operations Research|volum=5|număr=2|pagini=266–288|doi=10.1287/opre.5.2.266}}</ref> Versiunea lui sortează elementele în ordinea descrescătoare a valorii pe unitatea de greutate, <math>v_i/w_i</math>. 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ă <math /> este valoarea maximă de elemente care se încadrează în sac, atunci algoritmul greedy este garantat să obțină cel puțin o valoare de <math>m/2</math>. 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 ====
{{Ill-wd|Q843550|3=Schema de aproximare în timp polinomial complet}} (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, <math>v_i</math> și greutățile
  '''ieșire''':
    S', soluția FPTAS

  P := max <math /> // cea mai mare valoare
  K := ε <math />
  '''for''' i '''from''' 1 '''to''' n '''do'''
      <math>v'_i</math> := <math>\left\lfloor \frac{v_i}{K} \right\rfloor</math>
  '''end for'''
  '''return''' soluția, S', folosind valorile <math>v'_i</math> din programul dinamic prezentat mai sus
'''Teoremă:''' mulțimea <math>S'</math> calculată prin algoritmul de mai sus îndeplinește <math>\mathrm{profit}(S') \geq (1-\varepsilon) \cdot \mathrm{profit}(S^*)</math>, unde <math>S^*</math> 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:

<math>\qquad \sum_{j \in J} w_j\,x_j \ \le  \alpha\,w_i</math> și <math>\sum_{j \in J} v_j\,x_j \ \ge \alpha\,v_i\,</math> pentru un <math>x \in Z _+^n </math>

unde <math>\alpha\in Z_+ \,,J\subsetneq N</math> și <math>i\not\in J</math>. Vectorul {{math|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ă <math>i\ll J</math>, dacă greutatea totală a unei combinații de elemente din ''J'' este mai mică decât ''w<sub>i</sub>'' și valoarea lor totală este mai mare decât ''v<sub>i</sub>''.  Formal, <math>\sum_{j \in J} w_j\,x_j \ \le  w_i</math> și <math>\sum_{j \in J} v_j\,x_j \ \ge v_i</math> pentru un <math>x \in Z _+^n </math>, adică <math>\alpha=1</math>.  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 <math>V = v_i</math>, <math>W = w_i</math>, ș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 <math>i\prec\prec J</math>, dacă un număr de copii ale lui <math>i</math> sunt dominate de ''J''.  Formal, <math>\sum_{j \in J} w_j\,x_j \ \le  \alpha\,w_i</math>, și <math>\sum_{j \in J} v_j\,x_j \ \ge \alpha\,v_i\,</math> pentru un <math>x \in Z _+^n </math> și <math>\alpha\geq 1</math>.  Este o generalizare a dominanței colective, introdusă pentru prima oară în și utilizată în algoritmul EDUK.  Cel mai mic astfel de <math>\alpha</math> definește '''pragul''' elementului <math>i</math>, relație scrisă <math>t_i =(\alpha-1)w_i</math>.  În acest caz, soluția optimă ar putea conține cel mult <math>\alpha-1</math> copii ale lui <math>i</math>.
; Dominanța multiplă
: Al ''i''-lea element este '''multiplu dominat''' de un singur element <math>j</math>, relație scrisă ca <math>i\ll_{m} j</math>, dacă <math>i</math> este dominat de un număr de copii ale lui <math>j</math>.  Formal, <math>w_j\,x_j \ \le  w_i</math>, și <math>v_j\,x_j \ \ge v_i</math> pentru un <math>x_j \in Z _+ </math> adică <math> J=\{j\}, \alpha=1,  x_j=\lfloor \frac{w_i}{w_j}\rfloor</math>. Această dominanță poate fi utilizată eficient în preprocesare deoarece poate fi detectată relativ ușor.
; Dominanță modulară
: Fie ''b'' ''cel mai bun element'', adică <math>\frac{v_b}{w_b}\ge\frac{v_i}{w_i}\, </math> pentru orice <math>i</math>.  Acesta este elementul cu cea mai mare densitate de valoare. Al ''i''-lea element este '''modular dominat''' de un singur element <math>j</math>, relație scrisă ca <math>i\ll_\equiv j</math>, dacă <math>i</math> este dominat de <math>j</math> plus mai multe copii ale lui ''b''.  Formal, <math> w_j+tw_b \le w_i</math>, și  <math>v_j +tv_b \ge v_i </math> adică <math>J=\{b,j\}, \alpha=1,  x_b=t, x_j=1</math>.

== 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.<ref>Chang, T. J., et al. Heuristics for Cardinality Constrained Portfolio Optimization.
Technical Report, London SW7 2AZ, England: The Management School, Imperial
College, May 1998</ref><ref>Chang, C. S., et al. "Genetic Algorithm Based Bicriterion Optimization for Traction
Substations in DC Railway System." In Fogel [102], 11-16.</ref>

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 {{math|i}} este dată de un vector D-dimensional <math>\overline{w_i}=(w_{i1},\ldots,w_{iD})</math> și rucsacul are un vector de capacități D-dimensional <math>(W_1,\ldots,W_D)</math>. Obiectivul este de a maximiza suma valorilor elementelor în rucsac, astfel încât suma greutăților pe fiecare dimensiune {{math|d}} să nu depășească <math>W_d</math>.

Calculul problemei multi-dimensionale a rucsacului este mai greu decât cel al problemei simple; chiar și pentru <math>D=2</math> problema nu are nici măcar {{Ill-wd|Q843550|3=schemă de aproximare în timp polinomial}} decât dacă P<math>=</math>NP.<ref>{{Citat revistă|nume=Kulik|nume2=Shachnai|prenume=A.|prenume2=H.|an=2010|titlu=There is no EPTAS for two dimensional knapsack|journal=Inf. Process. Lett|volum=110|număr=16|pagini=707–710|doi=10.1016/j.ipl.2010.05.031}}</ref> Cu toate acestea, algoritmul din {{Harvnb|Cohen|Grebla|2014}}<ref name="CohenGrebla">Cohen, R. and Grebla, G. 2014. [http://wimnet.ee.columbia.edu/wp-content/uploads/2013/03/paper_short.pdf "Multi-Dimensional OFDMA Scheduling in a Wireless Network with Relay Nodes"]. in ''Proc. IEEE INFOCOM’14'', 2427–2435.</ref> este demonstrat a rezolva eficient cazurile rare. Un exemplu de problemă multi-dimensională a rucsacului este rară dacă există o mulțime <math>J=\{1,2,\ldots,m\}</math> pentru <math>m<D</math> astfel încât pentru fiecare element {{math|i}}, <math> \exists z>m</math> astfel încât <math>\forall j\in J\cup \{z\},\ w_{ij}\geq 0</math> și <math>\forall y\notin J\cup\{z\}, w_{iy}=0</math>. 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 unitate|pătrat unitar]] bidimensional): atunci când există cel mult cinci pătrate într-o acoperire optimă.<ref>Yan Lan, György Dósa, Xin Han, Chenyang Zhou, Attila Benkő [https://scholar.google.com/citations?user=txyI5aAAAAAJ]: ''2D knapsack: Packing squares'', Theoretical Computer Science Vol. 508, pp. 35–40.</ref>

=== Problema rucsacurilor multiple ===
Această variație este similară cu {{Ill-wd|Q814581|3=problema bin packing}}, 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.<ref>Chandra Chekuri și Sanjeev Khanna. 2000. A PTAS for the multiple knapsack problem. In Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms (SODA '00). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 213-222.</ref>

=== Problema rucsacului pătratică ===
Așa cum este descrisă de către Wu et al.:<blockquote class="" style="background-repeat: repeat; background-image: none; background-position: 0% 0%;">
Problema problema pătratică (QKP) maximizează o funcție obiectiv pătratică supusă unei constrângeri binare și liniare de capacitate.<ref name="QKP">{{Citat revistă|nume=Wu, Z. Y.|nume2=Yang, Y. J.|nume3=Bai, F. S.|nume4=Mammadov, M.|an=2011|titlu=Global Optimality Conditions and Optimization Methods for Quadratic Knapsack Problems|url=http://link.springer.com/article/10.1007/s10957-011-9885-4|journal=J Optim Theory Appl|volum=151|pagini=241&ndash;259|doi=10.1007/s10957-011-9885-4}}</ref>
</blockquote>Problema rucsacului pătratică fost discutată sub acest titlu de Gallo, Hammer și Simeone în 1980.<ref>{{Citat revistă|nume=Gallo, G.|nume2=Hammer, P. L.|nume3=Simeone, B.|an=1980|titlu=Quadratic knapsack problems|url=http://www.springerlink.com/content/x804231403086x51/|journal=Mathematical Programming Studies|volum=12|pagini=132&ndash;149|doi=10.1007/BFb0120892}}{{Legătură nefuncțională|date=octombrie 2022 |bot=InternetArchiveBot |fix-attempted=yes }}</ref> Gallo și Simeone<ref>{{Citat revistă|nume=Gallo, G.|nume2=Simeone, B.|an=1988|titlu=On the Supermodular Knapsack Problem|url=http://link.springer.com/article/10.1007%2FBF01589108?LI=true#page-1|journal=Mathematical Programming Studies|volum=45|pagini=295&ndash;309|publisher=North-Holland|doi=10.1007/bf01589108}}</ref> pun însă prima tratare a problemei pe seama lui Witzgall<ref>{{Citat carte|autor=Witzgall, C.|an=1975|titlu=Mathematical methods of site selection for Electronic Message Systems (EMS)|editură=NBS Internal report}}</ref> î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: <math>w_i=v_i</math>. În domeniul [[Criptografie|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]].<ref>Richard M. Karp (1972). </ref>

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.<ref>{{Citat revistă|nume=Caprara|nume2=Kellerer|nume3=Pferschy|prenume=Alberto|prenume2=Hans|prenume3=Ulrich|an=2000|titlu=The Multiple Subset Sum Problem|journal=SIAM J. on Optimization|volum=11|număr=2|pagini=308–319|doi=10.1137/S1052623498348481}}</ref>

== În cultura populară ==
* [[Neal Stephenson]] dă un exemplu de problema rucsacului în capitolul 70 din romanul său, ''{{Ill-wd|Q534975}},'' 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 & Dragons|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 [https://xkcd.com/287/ Web-comicul xkcd #287 intitulat "NP-Complete"]

== Note ==
<references />

== Bibliografie ==
* {{Citat carte|nume=Garey|autor2={{Ill-wd|Q92801}}|prenume=Michael R.|legătură-autor=Michael R. Garey|an=1979|titlu={{Ill-wd|Q938821}}|editură=W.H. Freeman|isbn=0-7167-1045-5}} A6: MP9, pg.247.
* <cite>{{Citat carte|autor=Kellerer, Hans|autor2=Pferschy, Ulrich|autor3=Pisinger, David|an=2004|titlu=Knapsack Problems|editură=Springer|isbn=3-540-40286-1|doi=10.1007/978-3-540-24777-7}}</cite>
* <cite>{{Citat carte|nume=Martello|nume2=Toth|prenume=Silvano|prenume2=Paolo|an=1990|titlu=Knapsack problems: Algorithms and computer implementations|editură=Wiley-Interscience|isbn=0-471-92420-2}}</cite>

== Legături externe ==
* [http://www.or.deis.unibo.it/knapsack.html Descărcare gratuită a cărții „Probleme ale rucsacului: algoritmi si implementări pe calculator”, de Silvano Martello și Paolo Toth] {{Webarchive|url=https://web.archive.org/web/20170506233616/http://www.or.deis.unibo.it/knapsack.html |date=2017-05-06 }}
* [http://www.cse.unl.edu/~goddard/Courses/CSCE310J/Lectures/Lecture8-DynamicProgramming.pdf Slide-uri de curs pe problema rucsacului]
* [http://download.gna.org/pyasukp PYAsUKP: Yet Another solver for the Unbounded Knapsack Problem] {{Webarchive|url=https://web.archive.org/web/20111006142943/http://download.gna.org/pyasukp/ |date=2011-10-06 }}, cu cod ce profită de relațiile de dominanță într-un algoritm hibrid,  teste de referință și copii descărcabile ale unor articole.
* [http://www.diku.dk/~pisinger/ 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?")
* [http://rosettacode.org/wiki/Knapsack_Problem Soluții la problema rucsacului în mai multe limbi] la {{Ill-wd|Q18056542}}
* [http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Dynamic/knapsackdyn.htm Algoritm de programare dinamică pentru problema rucsacului 0/1]
* [http://karaffeltut.com/NEWKaraffeltutCom/Knapsack/knapsack.html Site care rezolvă on-line problema rucsacului] {{Webarchive|url=https://web.archive.org/web/20140223114908/http://karaffeltut.com/NEWKaraffeltutCom/Knapsack/knapsack.html |date=2014-02-23 }}
* [http://www.nils-haldenwang.de/computer-science/computational-intelligence/genetic-algorithm-vs-0-1-knapsack Rezolvarea 0-1-RUCSAC cu algoritmi genetici în Ruby] {{Webarchive|url=https://web.archive.org/web/20110523210824/http://www.nils-haldenwang.de/computer-science/computational-intelligence/genetic-algorithm-vs-0-1-knapsack |date=2011-05-23 }}
* [http://www.adaptivebox.net/CILib/code/qkpcodes_link.html Coduri pentru problema rucsacului pătratică] {{Webarchive|url=https://web.archive.org/web/20150214020941/http://www.adaptivebox.net/CILib/code/qkpcodes_link.html |date=2015-02-14 }}

{{Portal|Matematică}}

[[Categorie:Probleme NP-complete]]
[[Categorie:Criptografie]]