Problema rucsacului

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare
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 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⁠(d) de dimensiune fixă cu elementele cele mai valoroase.

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.[1] Denumirea „problema rucsacului” datează de la începutul activității matematicianului Tobias Dantzig⁠(d) (1884–1956),[2] și se referă la problema banală de împachetare a celor mai valoroase sau utile elemente fără a supraîncărca bagajul.

Aplicații[modificare | modificare sursă]

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).[3]

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ă,[4] selecția de investiții și portofolii,[5] selecția de active titrizarea garantată cu active⁠(d),[6] și generarea de chei pentru Merkle–Hellman[7] ș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.[8]

Definiție[modificare | modificare sursă]

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[modificare | modificare sursă]

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,[9][10] 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.[11] 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[modificare | modificare sursă]

Sunt disponibili mai mulți algoritmi pentru rezolvarea problemei rucsacului, bazați pe abordarea cu programare dinamică,[12] branch and bound[13] sau cu hibridizări⁠(d) de ambele abordări.[14][15][16]

Algoritm de programare dinamică[modificare | modificare sursă]

Problema rucsacului nemărginită[modificare | modificare sursă]

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 W. Apoi, pentru fiecare , se definește  ca fiind valoarea maximă care poate fi atinsă cu greutatea totală mai mică sau egală cu w. 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 n elemente, și există W 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 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ă , nu cu W în sine.

Problema rucsacului 0/1[modificare | modificare sursă]

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 i (primele i 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:

 1 // Intrare:
 2 // Valori (stocate în tabloul v)
 3 // Greutăți (stocate în tabloul w)
 4 // Număr de elemente distincte (n)
 5 // Capacitatea rucsacului (W)
 6 
 7 for j from 0 to W do:
 8     m[0, j] := 0
 9 
10 for i from 1 to n do:
11     for j from 0 to W do:
12         if w[i] > j then:
13             m[i, j] := m[i-1, j]
14         else:
15             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[modificare | modificare sursă]

Un alt algoritm pentru problema 0/1 a rucsacului, descoperit în 1974 [17] ș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ă 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ă⁠(d)), 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  ș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

î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[modificare | modificare sursă]

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).[18]

Algoritm de aproximare greedy[modificare | modificare sursă]

George Dantzig a propus un algoritm greedy de aproximare⁠(d) pentru a rezolva problema rucsacului nemărginită.[19] Versiunea lui sortează elementele în ordinea descrescătoare a valorii pe unitatea de greutate, . 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ă este valoarea maximă de elemente care se încadrează în sac, atunci algoritmul greedy este garantat să obțină cel puțin o valoare de . 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[modificare | modificare sursă]

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,  și greutățile
 ieșire:
   S', soluția FPTAS
 P := max  // cea mai mare valoare
 K := ε 
 for i from 1 to n do
      := 
 end for
 return soluția, S', folosind valorile  din programul dinamic prezentat mai sus

Teoremă: mulțimea  calculată prin algoritmul de mai sus îndeplinește , unde  este o soluție optimă.

Relații de dominanță[modificare | modificare sursă]

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:

și pentru un 

unde  și . 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ă , dacă greutatea totală a unei combinații de elemente din J este mai mică decât wi și valoarea lor totală este mai mare decât vi. Formal, și  pentru un , adică . 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 , , ș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 , dacă un număr de copii ale lui  sunt dominate de J. Formal, , și  pentru un  și . Este o generalizare a dominanței colective, introdusă pentru prima oară în și utilizată în algoritmul EDUK. Cel mai mic astfel de  definește pragul elementului , relație scrisă . În acest caz, soluția optimă ar putea conține cel mult  copii ale lui .
Dominanța multiplă
Al i-lea element este multiplu dominat de un singur element , relație scrisă ca , dacă  este dominat de un număr de copii ale lui . Formal, , și  pentru un  adică . Această dominanță poate fi utilizată eficient în preprocesare deoarece poate fi detectată relativ ușor.
Dominanță modulară
Fie b cel mai bun element, adică  pentru orice . Acesta este elementul cu cea mai mare densitate de valoare. Al i-lea element este modular dominat de un singur element , relație scrisă ca , dacă  este dominat de  plus mai multe copii ale lui b. Formal, , și   adică .

Variații[modificare | modificare sursă]

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[modificare | modificare sursă]

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.[20][21]

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ă[modificare | modificare sursă]

În această variantă, greutatea elementului i este dată de un vector D-dimensional și rucsacul are un vector de capacități D-dimensional . Obiectivul este de a maximiza suma valorilor elementelor în rucsac, astfel încât suma greutăților pe fiecare dimensiune d să nu depășească .

Calculul problemei multi-dimensionale a rucsacului este mai greu decât cel al problemei simple; chiar și pentru problema nu are nici măcar schemă de aproximare în timp polinomial⁠(d) decât dacă PNP.[22] Cu toate acestea, algoritmul din Cohen & Grebla 2014[23] este demonstrat a rezolva eficient cazurile rare. Un exemplu de problemă multi-dimensională a rucsacului este rară dacă există o mulțime  pentru astfel încât pentru fiecare element i, astfel încât  și . 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ă.[24]

Problema rucsacurilor multiple[modificare | modificare sursă]

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.[25]

Problema rucsacului pătratică[modificare | modificare sursă]

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.[26]

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

Problema sumei submulțimilor[modificare | modificare sursă]

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: . Î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.[30]

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.[31]

În cultura populară[modificare | modificare sursă]

  • 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[modificare | modificare sursă]

  1. ^ Mathews, G. B. (25 iunie 1897). „On the partition of numbers”. Proceedings of the London Mathematical Society 28: 486–490. doi:10.1112/plms/s1-28.1.486. http://plms.oxfordjournals.org/content/s1-28/1/486.full.pdf. 
  2. ^ Dantzig, Tobias. Numbers: The Language of Science, 1930.
  3. ^ Skiena, S. S. (1 septembrie 1999). „Who is Interested in Algorithms and Why? Lessons from the Stony Brook Algorithm Repository”. AGM SIGACT News 30 (3): 65–74. doi:10.1145/333623.333627. ISSN 0163-5700. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41.8357&rep=rep1&type=pdf. 
  4. ^ Kellerer, Pferschy, and Pisinger 2004, p. 449
  5. ^ Kellerer, Pferschy, and Pisinger 2004, p. 461
  6. ^ Kellerer, Pferschy, and Pisinger 2004, p. 465
  7. ^ Kellerer, Pferschy, and Pisinger 2004, p. 472
  8. ^ Feuerman, Martin; Weiss, Harvey (1 aprilie 1973). „A Mathematical Programming Model for Test Construction and Scoring”. Management Science 19 (8): 961–966. doi:10.1287/mnsc.19.8.961. 
  9. ^ Pisinger, D. 2003.
  10. ^ Caccetta, L.; Kulanoot, A. (2001). „Computational Aspects of Hard Knapsack Problems”. Nonlinear Analysis 47: 5547–5558. doi:10.1016/s0362-546x(01)00658-7. 
  11. ^ Poirriez, Vincent; Yanev, Nicola; Andonov, Rumen (2009). „A hybrid algorithm for the unbounded knapsack problem”. Discrete Optimization 6 (1): 110–124. doi:10.1016/j.disopt.2008.09.004. ISSN 1572-5286. 
  12. ^ Andonov, Rumen; Poirriez, Vincent; Rajopadhye, Sanjay (2000). „Unbounded Knapsack Problem : dynamic programming revisited”. European Journal of Operational Research 123 (2): 168–181. doi:10.1016/S0377-2217(99)00265-9. 
  13. ^ S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations, John Wiley and Sons, 1990
  14. ^ S. Martello, D. Pisinger, P. Toth, Dynamic programming and strong bounds for the 0-1 knapsack problem, Manag.
  15. ^ Plateau, G.; Elkihel, M. (1985). „A hybrid algorithm for the 0-1 knapsack problem”. Methods of Oper. Res. 49: 277–293. 
  16. ^ Martello, S.; Toth, P.. „A mixture of dynamic programming and branch-and-bound for the subset-sum problem”. Manag. Sci. 30: 765–771. doi:10.1287/mnsc.30.6.765. 
  17. ^ Horowitz, Ellis; Sahni, Sartaj (1974), „Computing partitions with applications to the knapsack problem”, Journal of the Association for Computing Machinery 21: 277–292, doi:10.1145/321812.321823 
  18. ^ Vazirani, Vijay. Approximation Algorithms. Springer-Verlag Berlin Heidelberg, 2003.
  19. ^ Dantzig, George B. (1957). „Discrete-Variable Extremum Problems”. Operations Research 5 (2): 266–288. doi:10.1287/opre.5.2.266. 
  20. ^ Chang, T. J., et al. Heuristics for Cardinality Constrained Portfolio Optimization. Technical Report, London SW7 2AZ, England: The Management School, Imperial College, May 1998
  21. ^ Chang, C. S., et al. "Genetic Algorithm Based Bicriterion Optimization for Traction Substations in DC Railway System." In Fogel [102], 11-16.
  22. ^ Kulik, A.; Shachnai, H. (2010). „There is no EPTAS for two dimensional knapsack”. Inf. Process. Lett 110 (16): 707–710. doi:10.1016/j.ipl.2010.05.031. 
  23. ^ Cohen, R. and Grebla, G. 2014. "Multi-Dimensional OFDMA Scheduling in a Wireless Network with Relay Nodes". in Proc. IEEE INFOCOM’14, 2427–2435.
  24. ^ Yan Lan, György Dósa, Xin Han, Chenyang Zhou, Attila Benkő [1]: 2D knapsack: Packing squares, Theoretical Computer Science Vol. 508, pp. 35–40.
  25. ^ 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.
  26. ^ Wu, Z. Y.; Yang, Y. J.; Bai, F. S.; Mammadov, M. (2011). „Global Optimality Conditions and Optimization Methods for Quadratic Knapsack Problems”. J Optim Theory Appl 151: 241–259. doi:10.1007/s10957-011-9885-4. http://link.springer.com/article/10.1007/s10957-011-9885-4. 
  27. ^ Gallo, G.; Hammer, P. L.; Simeone, B. (1980). „Quadratic knapsack problems”. Mathematical Programming Studies 12: 132–149. doi:10.1007/BFb0120892. http://www.springerlink.com/content/x804231403086x51/. 
  28. ^ Gallo, G.; Simeone, B. (1988). „On the Supermodular Knapsack Problem”. Mathematical Programming Studies (North-Holland) 45: 295–309. doi:10.1007/bf01589108. http://link.springer.com/article/10.1007%2FBF01589108?LI=true#page-1. 
  29. ^ Witzgall, C. (1975). Mathematical methods of site selection for Electronic Message Systems (EMS). NBS Internal report 
  30. ^ Richard M. Karp (1972).
  31. ^ Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000). „The Multiple Subset Sum Problem”. SIAM J. on Optimization 11 (2): 308–319. doi:10.1137/S1052623498348481. 

Bibliografie[modificare | modificare sursă]

Legături externe[modificare | modificare sursă]