Problema rucsacului

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 Format:Ill-wd: 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 Format:Ill-wd unde există constrângeri financiare și este studiată în domenii cum ar fi combinatorica, informatica, teoria complexității, criptografia, matematicile aplicate și Format:Ill-wd.

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 Format:Ill-wd (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

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ă Format:Ill-wd, Format:Ill-wd, și Format:Ill-wd.^[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 Format:Ill-wd,^[6] și generarea de chei pentru Merkle–Hellman^[7] și alte Format:Ill-wd.

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

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 de exemplare din fiecare tip de articol la o valoare maximă întreagă 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

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 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 Format:Ill-wd 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 Format:Ill-wd ce folosește Format:Ill-wd.
Există Format:Ill-wd, 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

Sunt disponibili mai mulți algoritmi pentru rezolvarea problemei rucsacului, bazați pe abordarea cu programare dinamică,^[12] branch and bound^[13] sau cu Format:Ill-wd de ambele abordări.^[14]^[15]^[16]

Algoritm de programare dinamică

Problema rucsacului nemărginită

Dacă toate greutățile ( $w_{1}, \dots, 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 Format:Math. 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 Format:Math. 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 Format:Math elemente, și există Format:Math valori ale lui $m [w]$ de calculat, timpul de rulare a soluției de programare dinamică este $O (n W)$ . Împărțirea $w_{1}, w_{2}, \dots, 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 (n W)$ nu contrazice faptul că problema rucsacului este NP-completă, deoarece Format:Math, spre deosebire de Format:Math, nu este polinomial în lungimea de intrare a problemei. Lungimea intrării Format:Math a problemei este proporțională cu numărul de biți din Format:Math, adică $\log W$ , nu cu Format:Math î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}, \dots, 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 Format:Math (primele Format:Math 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} ⩽ 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 (n W)$ și în spațiu $O (n W)$ >. Î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 ^[17] și uneori numit „meet-in-the-middle” din cauza paralelor cu Format:Ill-wd, este exponențială în numărul de elemente diferite, dar poate fi de preferat față de algoritmul PD atunci când Format:Math 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 Format:Ill-wd (de exemplu, folosind aritmetica în virgulă fixă), dar dacă problema necesită Format:Math cifre fracționare de precizie pentru a ajunge la răspunsul corect, Format:Math va trebui să fie scalat cu un factor de $1 0^{d}$ și algoritmul PD va avea nevoie de un spațiu de $O (W 1 0^{d})$ și de un timp de $O (n W 1 0^{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 (n 2^{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).^[18]

Algoritm de aproximare greedy

George Dantzig a propus un Format:Ill-wd pentru a rezolva problema rucsacului nemărginită.^[19] 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ă 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

Format:Ill-wd (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  // cea mai mare valoare
 K := ε 
 for i from 1 to n do
      $v'_{i}$  :=  $⌊ \frac{v_{i}}{K} ⌋$ 
 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 $p r o f i t (S^{'}) \geq (1 - ε) \cdot p r o f i t (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:

$\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}$

unde $α \in Z_{+}, J ⊊ N$ și $i \in̸ J$ . Vectorul Format:Math 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 ≪ 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ă $α = 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 ≺ ≺ J$ , dacă un număr de copii ale lui $i$ sunt dominate de J. 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}$ și $α \geq 1$ . 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 $i$ , relație scrisă $t_{i} = (α - 1) w_{i}$ . În acest caz, soluția optimă ar putea conține cel mult $α - 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 ≪_{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}, α = 1, x_{j} = ⌊ \frac{w_{i}}{w_{j}} ⌋$ . 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 ≪_{\equiv} j$ , dacă $i$ este dominat de $j$ plus mai multe copii ale lui b. Formal, $w_{j} + t w_{b} \leq w_{i}$ , și $v_{j} + t v_{b} \geq v_{i}$ adică $J = {b, j}, α = 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.^[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ă

În această variantă, greutatea elementului Format:Math este dată de un vector D-dimensional $\overline{w_{i}} = (w_{i 1}, \dots, w_{i D})$ și rucsacul are un vector de capacități D-dimensional $(W_{1}, \dots, W_{D})$ . Obiectivul este de a maximiza suma valorilor elementelor în rucsac, astfel încât suma greutăților pe fiecare dimensiune Format:Math 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 Format:Ill-wd decât dacă P $=$ NP.^[22] Cu toate acestea, algoritmul din Format:Harvnb^[23] 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, \dots, m}$ pentru $m < D$ astfel încât pentru fiecare element Format:Math, $\exists z > m$ astfel încât $\forall j \in J \cup {z}, w_{i j} \geq 0$ și $\forall y \notin J \cup {z}, w_{i y} = 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ă.^[24]

Problema rucsacurilor multiple

Această variație este similară cu Format:Ill-wd, 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ă

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

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.^[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ă

Neal Stephenson dă un exemplu de problema rucsacului în capitolul 70 din romanul său, Format:Ill-wd, 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

↑ Format:Cite journal
↑ Dantzig, Tobias. Numbers: The Language of Science, 1930.
↑ Format:Cite journal
↑ Kellerer, Pferschy, and Pisinger 2004, p. 449
↑ Kellerer, Pferschy, and Pisinger 2004, p. 461
↑ Kellerer, Pferschy, and Pisinger 2004, p. 465
↑ Kellerer, Pferschy, and Pisinger 2004, p. 472
↑ Format:Cite journal
↑ Pisinger, D. 2003.
↑ Format:Cite journal
↑ Format:Cite journal
↑ Format:Cite journal
↑ S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations, John Wiley and Sons, 1990
↑ S. Martello, D. Pisinger, P. Toth, Dynamic programming and strong bounds for the 0-1 knapsack problem, Manag.
↑ Format:Cite journal
↑ Format:Cite journal
↑ Format:Citation
↑ Vazirani, Vijay. Approximation Algorithms. Springer-Verlag Berlin Heidelberg, 2003.
↑ Format:Citat revistă
↑ Chang, T. J., et al. Heuristics for Cardinality Constrained Portfolio Optimization. Technical Report, London SW7 2AZ, England: The Management School, Imperial College, May 1998
↑ Chang, C. S., et al. "Genetic Algorithm Based Bicriterion Optimization for Traction Substations in DC Railway System." In Fogel [102], 11-16.
↑ Format:Citat revistă
↑ Cohen, R. and Grebla, G. 2014. "Multi-Dimensional OFDMA Scheduling in a Wireless Network with Relay Nodes". in Proc. IEEE INFOCOM’14, 2427–2435.
↑ 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.
↑ 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.
↑ Format:Citat revistă
↑ Format:Citat revistă Format:Legătură nefuncțională
↑ Format:Citat revistă
↑ Format:Citat carte
↑ Richard M. Karp (1972).
↑ Format:Citat revistă

Bibliografie

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 Format:Webarchive
Slide-uri de curs pe problema rucsacului
PYAsUKP: Yet Another solver for the Unbounded Knapsack Problem Format:Webarchive, 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 Format:Ill-wd
Algoritm de programare dinamică pentru problema rucsacului 0/1
Site care rezolvă on-line problema rucsacului Format:Webarchive
Rezolvarea 0-1-RUCSAC cu algoritmi genetici în Ruby Format:Webarchive
Coduri pentru problema rucsacului pătratică Format:Webarchive

Format:Portal

[1] Format:Cite journal

[2] Dantzig, Tobias. Numbers: The Language of Science, 1930.

[3] Format:Cite journal

[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] Format:Cite journal

[pisinger200308-9] Pisinger, D. 2003.

[Cacetta2001-10] Format:Cite journal

[poirriez_et_all_2009-11] Format:Cite journal

[eduk2000-12] Format:Cite journal

[martellototh90-13] S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations, John Wiley and Sons, 1990

[martellopisingertoth99a-14] S. Martello, D. Pisinger, P. Toth, Dynamic programming and strong bounds for the 0-1 knapsack problem, Manag.

[plateau85-15] Format:Cite journal

[martellotothe99-16] Format:Cite journal

[17] Format:Citation

[Vazirani,_Vijay_2003-18] Vazirani, Vijay. Approximation Algorithms. Springer-Verlag Berlin Heidelberg, 2003.

[dantzig1957-19] Format:Citat revistă

[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] Format:Citat revistă

[CohenGrebla-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.

[QKP-26] Format:Citat revistă

[27] Format:Citat revistă Format:Legătură nefuncțională

[28] Format:Citat revistă

[29] Format:Citat carte

[30] Richard M. Karp (1972).

[31] Format:Citat revistă

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

Problema rucsacului

Cuprins

Aplicații

Definiție

Complexitatea de calcul

Rezolvarea

Algoritm de programare dinamică

Problema rucsacului nemărginită

Problema rucsacului 0/1

Meet-in-the-middle

Algoritmi de aproximare

Algoritm de aproximare greedy

Schema de aproximare în timp polinomial complet

Relații de dominanță

Variații

Problema rucsacului multiobiectiv

Problema rucsacului multidimensională

Problema rucsacurilor multiple

Problema rucsacului pătratică

Problema sumei submulțimilor

În cultura populară

Note

Bibliografie

Legături externe

Meniu de navigare

Problema rucsacului

Aplicații

Definiție

Complexitatea de calcul

Rezolvarea

Algoritm de programare dinamică

Problema rucsacului nemărginită

Problema rucsacului 0/1

Meet-in-the-middle

Algoritmi de aproximare

Algoritm de aproximare greedy

Schema de aproximare în timp polinomial complet

Relații de dominanță

Variații

Problema rucsacului multiobiectiv

Problema rucsacului multidimensională

Problema rucsacurilor multiple

Problema rucsacului pătratică

Problema sumei submulțimilor

În cultura populară

Note

Bibliografie

Legături externe

Meniu de navigare

Căutare