Problema rucsacului

Problema rucsacului (de asemenea, problema rucsacului ) este o problemă de optimizare combinatorie NP-completă . Și-a luat numele de la scopul final: să pună cât mai multe lucruri de valoare într-un rucsac, cu condiția ca capacitatea ghiozdanului să fie limitată. Diferite variații ale problemei rucsacului pot fi întâlnite în economie , matematică aplicată , criptografie și logistică .

În general, problema poate fi formulată astfel: dintr-un set dat de articole cu proprietățile „cost” și „greutate”, este necesar să se selecteze un subset cu costul total maxim, cu respectarea restricției asupra greutății totale.

Enunțul clasic al problemei

Să existe un set de obiecte, fiecare dintre ele având doi parametri - masa și valoarea. Există și un rucsac cu o anumită capacitate de transport. Sarcina este de a construi un rucsac cu valoarea maximă a obiectelor din interior, respectând în același timp limita de masă totală a rucsacului.

Matematic, problema este formulată astfel: există marfă. Pentru fiecare sarcină se determină masa și valoarea acesteia . Limita greutății totale a articolelor dintr-un rucsac este stabilită de capacitatea de transport . Necesar $n$ $i$ $w_{i}>0$ $v_{i}>0$ $i=1,2,...,n$ $W$

maximiza

\sum _{i=1}^{n}v_{i}x_{i}

cu restricţii şi [1] .

\sum _{i=1}^{n}w_{i}x_{i}\leq W

x_{i}\in \{0,1\}

Variante ale problemei rucsacului

Enunțul problemei permite un număr mare de generalizări, în funcție de condițiile impuse rucsacului, obiectelor sau alegerea acestora. Cele mai populare soiuri sunt următoarele:

Rucsac 0-1 ( ing. 0-1 Problemă rucsac ) [2] : nu mai mult de o copie a fiecărui articol.
Problemă de rucsac delimitată [3] : nu mai mult de un număr dat de cazuri ale fiecărui articol.
Problemă de rucsac nemărginit [3] : Un număr arbitrar de instanțe ale fiecărui articol.
Problemă la rucsac cu alegere multiplă [ 4] : Articolele sunt împărțite în grupuri și trebuie selectat doar un articol din fiecare grup.
Problemă cu rucsacuri multiple [5] : Există mai multe rucsacuri, fiecare cu propria sa greutate maximă. Fiecare articol poate fi pus în orice rucsac sau lăsat.
Problemă de rucsac multidimensional : în loc de greutate, sunt date mai multe resurse diferite (de exemplu, greutatea, volumul și timpul de stivuire). Fiecare articol cheltuiește o anumită cantitate din fiecare resursă. Este necesar să alegeți un subset de articole astfel încât costul total al fiecărei resurse să nu depășească maximul pentru această resursă, iar în același timp valoarea totală a articolelor să fie maximă [4] .
Problemă de rucsac patratic : valoarea totală este dată de o formă pătratică definită nenegativă [6] .

Problemă neliniară la rucsac

Una dintre cele mai generale variante ale problemei rucsacului este cea neliniară . Poate fi formulat astfel:

Lăsați vectorul să determine numărul de instanțe ale fiecărui articol din rucsac. Atunci problema este să găsim minimul funcției $x=(x_{1},..,x_{n})\in \mathbb {R} ^{n)$

$\min _{x\in S}\f(x)$ ,

cu o constrângere dată:

$g(x)\leq b$ .

Se presupune că funcțiile sunt continue și diferențiabile pe . este o constantă întreagă , mulțimea este nevide [7] . $f(x),g(x):\mathbb {R} ^{n}\rightarrow \mathbb {R}$ $\mathbb {R} ^{n}$ $b$ $S$

În cazul funcțiilor liniare , problema se reduce la una din formulările clasice, în funcție de mulțime : $f(x),g(x)$ $S$

$S=\{0,1\}^{n)$ - rucsac 0-1
$S=\mathbb {N_{0}} ^{n}$ - rucsac nelimitat
$S=\{(x_{1},..,x_{n})\in \mathbb {N_{0}} ^{n}:x_{i}\leq c_{i}\}$ - rucsac limitat

Libertatea în alegerea funcțiilor permite rezolvarea unei clase mai largi de sarcini, inclusiv organizarea instalațiilor de producție $f(x),g(x)$ , distribuția optimă a probelor într-o probă regionalizată , sau soluția problemei rucsacului patratic [7] .

Metode exacte de rezolvare

După cum am menționat mai sus, problema rucsacului aparține clasei NP-complete și până acum nu a fost găsit un algoritm polinomial pentru ea care să o rezolve într-un timp rezonabil. Prin urmare, atunci când se rezolvă problema rucsacului, este necesar să se aleagă între algoritmi exacti, care nu sunt aplicabili la rucsacuri „mari”, și cei aproximativi, care funcționează rapid, dar nu garantează soluția optimă a problemei.

Enumerarea completă

Ca și în cazul altor probleme discrete , problema rucsacului poate fi rezolvată prin enumerarea exhaustivă a tuturor soluțiilor posibile.

În funcție de starea problemei, există articole care pot fi puse într-un rucsac și trebuie să determinați costul maxim al încărcăturii, a cărei greutate nu depășește . $N$ $W$

Pentru fiecare articol, există 2 opțiuni: articolul este pus în rucsac, sau articolul nu este pus în rucsac. Atunci enumerarea tuturor opțiunilor posibile are complexitate de timp , ceea ce îi permite să fie utilizat doar pentru un număr mic de articole [8] . Odată cu creșterea numărului de obiecte, problema devine de nerezolvată prin această metodă într-un timp acceptabil. $O(2^{N})$

Figura prezintă un arbore de iterație pentru trei elemente. Fiecare frunză corespunde unui subset de articole. După alcătuirea arborelui, este necesar să se găsească o frunză cu valoarea maximă dintre cele a căror greutate nu depășește [9] . $W$

Branch and Bound Method

Metoda ramurilor și legate este o variație a metodei forței brute, cu diferența că ramurile neoptimale ale arborelui forței brute sunt excluse. La fel ca metoda forței brute, vă permite să găsiți soluția optimă și, prin urmare, aparține algoritmilor exacti.

Algoritmul original, propus de Peter Kolesar în 1967, propune sortarea articolelor după costul lor unitar (raportul dintre valoare și greutate) și construirea unui arbore cu forță brută . Îmbunătățirea sa constă în faptul că în procesul de construire a unui arbore pentru fiecare nod se estimează o limită superioară a valorii soluției, iar construcția arborelui continuă doar pentru nodul cu estimarea maximă [10] . Când limita superioară maximă este într-o frunză a arborelui, algoritmul își încheie activitatea.

Capacitatea de ramificare și legat de a reduce numărul de iterații se bazează în mare măsură pe datele de intrare. Este recomandabil să îl utilizați numai dacă valorile specifice ale articolelor diferă semnificativ [11] .

Metode de programare dinamică

Problema rucsacului nemărginit

Cu o constrângere suplimentară asupra greutăților articolelor, problema rucsacului poate fi rezolvată în timp pseudopolinom folosind metode de programare dinamică .

Fie ponderea fiecărui element un număr întreg pozitiv. Apoi, pentru a rezolva problema, este necesar să se calculeze soluțiile optime pentru toate , unde este capacitatea de încărcare dată. Să definim ca fiind valoarea maximă a articolelor care pot fi plasate într-un rucsac cu o capacitate de transport de . $w_{i}$ $w\in \mathbb {Z} :0\leq w\leq W$ $W$ $m[w]$ $w$

Pentru că puteți scrie formule recursive : $m[w]$

$m[0]=0$
$m[w]=\max _{w_{i}\leq w}(v_{i}+m[w-w_{i}])$ [12] ,

unde sunt valoarea și , respectiv, greutatea elementului --lea, iar maximul din setul gol ar trebui considerat egal cu zero. $v_{i},w_{i}$ $i$

De fapt, ultima ecuație este ecuația funcțională a lui R. Bellman sau ecuația funcțională a programării dinamice. În acest caz, pentru a o rezolva, este suficient să calculați toate valorile lui , începând de la și până la [12] . Dacă în plus stocăm la fiecare pas un set de articole care realizează valoarea maximă, atunci algoritmul va oferi și setul optim de articole. $m[w]$ $0$ $W$

Deoarece la fiecare pas este necesar să se găsească maximul itemilor, algoritmul are o complexitate de calcul de . Deoarece poate depinde exponențial de dimensiunea intrării, algoritmul este pseudopolinom . Prin urmare, eficiența acestui algoritm este determinată de valoarea lui . Algoritmul dă rezultate excelente pentru , dar nu foarte bune pentru [13] . $n$ $O(nW)$ $W$ $W$ $W\leq 1000$ $W\geq 10\000\000$

Problemă la rucsac 0-1

Soluția problemei rucsacului 0-1 este aproape de soluția problemei anterioare, dar este necesar să se țină cont de faptul că fiecare articol se află într-un singur exemplar. Fie valoarea maximă a articolelor obținute din primele articole disponibile, cu o greutate totală care nu depășește . $m[i,w]$ $i$ $w$

Relații recurente :

$m[0,w]=0$
$m[i,\,w]=m[i-1,\,w]$ , dacă $w_{i}>w$
$m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ , dacă $w_{i}\leq w$

Calculând , puteți găsi soluția exactă. Dacă matricea se potrivește în memoria mașinii, atunci acest algoritm este probabil unul dintre cele mai eficiente [12] . $m[n,W]$ $m[i,w]$

// Intrare: // Valorile articolului (încărcate în matricea v) // Greutăți articole (încărcate în matricea w) // Număr de articole (n) // Capacitate de încărcare (W) pentru j de la 0 la W fac : m [ 0 , j ] := 0 pentru i de la 1 la n fac : pentru j de la 0 la W fac : dacă w [ i ] > j atunci : m [ i , j ] := m [ i -1 , j ] altceva : m [ i , j ] := max ( m [ i -1 , j ], m [ i -1 , j - w [ i ]] + v [ i ])

Soluția poate fi ilustrată prin programare dinamică după cum urmează: pe un plan bidimensional, numărul de obiecte este reprezentat de-a lungul axei , iar greutatea lor este reprezentată de-a lungul axei. La prima etapă se construiesc două linii de la originea coordonatelor: una orizontală, corespunzătoare faptului că nu a fost luat primul obiect, și una înclinată, corespunzătoare primului obiect luat. Proiecțiile lor pe axă sunt egale cu greutatea obiectului. La a doua etapă se construiesc din nou 2 linii, orizontale (al doilea obiect nu a fost luat) sau oblice (al doilea obiect a fost luat). Să setăm lungimea arcelor orizontale la zero, iar lungimea arcelor oblice la valoarea obiectului [14] . Astfel, orice soluție a problemei corespunde unei căi în arborele construit . Problema se reduce la găsirea unei căi de lungime maximă [14] . Lăsați capacitatea rucsacului . $X$ $Y$ $Y$ $W=14$

Numărul de articol	Valoare	Greutatea
unu	3	5
2	5	zece
3	patru	6
patru	2	5

Din figură se poate observa că valoarea totală pentru soluția optimă este 7, deoarece aceasta este valoarea maximă din arborele construit.

Programare dinamică asupra valorilor articolelor

Relațiile de recurență pot fi scrise nu numai în ceea ce privește greutatea obiectelor, ci și în ceea ce privește valoarea. Pentru a face acest lucru, notăm ponderea minimă a articolelor cu valoarea totală , care poate fi obținută de la primele articole. Dacă greutatea necesară nu poate fi obținută, marcați-o ca . $y[i,V]$ $V$ $i$ $y[i,V]=W+1$

După aceea, rezolvăm ecuația de programare dinamică funcțională :

$y[i,V]={\begin{cases}y[i-1,V],&{\text{if }}V<v_{i}\\\min\{\y[i- 1,V],y[i-1,V-v_{i}]+w_{i}\},&{\text{if }}V\geq v_{i}\end{cases}}$ ,

cu conditiile initiale :

$y[0,0]=0$

$y[0,V]=W+1$ [cincisprezece]

Metode aproximative de rezolvare

Ca și în cazul majorității problemelor NP-complete, nu este întotdeauna necesar să se obțină o soluție exactă, deoarece soluțiile care sunt aproape de optime pot fi aplicate în probleme aplicate.

Algoritm lacom

Pentru a rezolva problema cu un algoritm lacom , este necesar să sortați lucrurile după valoarea lor specifică (adică raportul dintre valoarea unui articol și greutatea acestuia) și să plasați articolele cu cea mai mare valoare specifică în rucsac [10] .

Timpul de rulare al acestui algoritm este suma timpului de sortare și timpul de stivuire. Complexitatea sortării articolelor este de . Apoi, calculează câte articole vor încăpea în rucsac în timpul total [10] . Complexitatea rezultată atunci când sortarea este necesară și când datele sunt deja sortate [10] . $O(N\log(N))$ $O(N)$ $O(N\log(N))$ $O(N)$

Exemplu . Lăsați capacitatea rucsacului . Articolele sunt deja sortate după valoarea unitară. Să folosim algoritmul lacom. $W=80$

i	greutatea	Preț	pret/greutate
unu	cincisprezece	60	patru
2	treizeci	90	3
3	cincizeci	100	2

Punem primul articol în rucsac, iar după el al doilea. Al treilea articol nu va intra în rucsac. Valoarea totală a articolelor din rucsac este de 150. Dacă s-ar lua al doilea și al treilea articol, valoarea totală ar fi 190. Astfel, am obținut o soluție neoptimală.

Trebuie înțeles că un algoritm lacom poate duce la un răspuns arbitrar departe de cel optim. De exemplu, dacă un articol are o pondere de 1 și un cost de 2, iar celălalt are o pondere de W și un cost de W, atunci algoritmul lacom va nota un cost total de 2 cu un răspuns optim de W. La în același timp, același algoritm pentru problema rucsacului nemărginit va conduce la un răspuns de cel puțin 50% din valoarea optimului [10] .

Algoritmul greedy a fost propus pentru prima dată de George Danzig [16] pentru a rezolva problema nemărginită a rucsacului.

Schema aproximativă pentru timpul complet polinomial

Deoarece nu a fost găsit algoritmul exact pentru rezolvarea problemei în timp polinomial , problema a apărut pentru a obține o soluție polinomială cu precizie garantată . Pentru a face acest lucru, există o serie de scheme aproximative de timp complet polinom , adică cu complexitate care este un polinom în și . $1-\varepsilon$ $n$ ${\frac {1}{\varepsilon }}$

Ideea din spatele schemei clasice este de a reduce precizia cu care sunt date valorile articolelor. Combinând articole de valoare similară într-un singur grup, puteți reduce numărul de articole diferite. Algoritmul se scrie astfel [15] :

Să găsim o soluție aproximativă folosind un algoritm lacom. Să fie soluția exactă. Apoi din estimarea eficienței algoritmului greedy . $x^{l)$ $x^{*}$ $x^{l}\leq x^{*}\leq 2x^{l)$
Scalați valorile după cum urmează: . $v'_{i}=\left\lfloor {\frac {v_{i}}{\frac {x^{l}\varepsilon }{n}}}\right\rfloor$
Folosind algoritmul de programare dinamică pentru o problemă cu valori întregi ale obiectelor, găsim o soluție.

Există multe scheme diferite de aproximare. Cu toate acestea, ele depind puternic de formularea problemei rucsacului. De exemplu, dacă în condiție apare o a doua constrângere de tip inegalitate (rucsac bidimensional), atunci problema nu mai are o schemă de timp polinomială cunoscută [17] .

Algoritmi genetici

Ca și în cazul altor probleme de optimizare NP-hard, algoritmii genetici sunt utilizați pentru a rezolva problema rucsacului . Nu garantează găsirea soluției optime în timp polinomial și nu oferă o estimare a proximității soluției față de cea optimă, dar au indicatori buni de timp, permițându-vă să găsiți o soluție destul de bună mai rapid decât alte deterministe sau euristice cunoscute. metode. [optsprezece]

Fiecare individ ( genotip ) este un subset al articolelor pe care dorim să le împachetăm în ghiozdan (greutatea lor totală poate depăși capacitatea de transport admisă). Pentru comoditate, informațiile sunt stocate ca șiruri binare, în care fiecare bit determină dacă acest articol se potrivește într-un ghiozdan [19] .

Funcția de fitness determină apropierea soluției de cea optimă. De exemplu, valoarea totală a articolelor poate servi ca atare, cu condiția ca greutatea totală să nu depășească capacitatea de transport.

După o serie de schimbări generaționale în care cei mai apți indivizi sunt încrucișați , iar restul sunt ignorați, algoritmul ar trebui să îmbunătățească soluțiile originale [19] .

Rezolvarea problemei sumei submulțimii

Un caz special al problemei rucsacului 0-1 este problema sumei subsetului . Fie capacitatea de transport a rucsacului, greutatea celui de-al -lea articol și costul acestuia . Astfel, sarcina este să încărcați rucsacul cât mai strâns posibil sau să epuizați complet resursele: $W$ $w_{i}$ $i$ $v_{i}=w_{i}$

$W=\sum _{i=1}^{N}w_{i}x_{i},\qquad \ x_{i}\in \{0,1\}$

Pentru a o rezolva, puteți folosi algoritmul genetic menționat . Un individ este un vector . Ca funcție de fitness, ar trebui să se folosească proximitatea greutății totale a obiectelor de , cu singura caracteristică că seturile care se potrivesc într-un rucsac sunt mai de preferat (greutatea totală a obiectelor este mai mică de ) [19] . $(x_{1},...,x_{n})$ $W$ $W$

Să definim formal funcția de fitness . Fie suma greutăților tuturor articolelor. Apoi - abaterea maximă posibilă a greutății articolelor din rucsac de la . $f(x_{1},..,x_{n}):\{0,1\}^{n}\rightarrow \mathbb {R}$ $\mathcal{S}$ ${\textstyle \Delta _{max}=max(W,{\mathcal {S}}-W)}$ $W$

Fie greutatea totală a elementelor pentru vectorul dat. Apoi punem: ${\textstyle W'=\sum _{i=1}^{N}w_{i}x_{i}}$

$f(x_{1},..,x_{n})={\begin{cases}1-{\sqrt {\frac {WW'}{W)}},&W'\leq W,\ \1-{\sqrt {\frac {W'-W}{\Delta _{max)))),&W'>W.\end{cases))$ [19]

Folosind algoritmul general, putem găsi o soluție aproximativă:

Creați un set aleatoriu de indivizi - o populație.
Calculați funcția de adaptare pentru fiecare individ.
Lăsați doar cei mai apți indivizi (selecție naturală).
Efectuați încrucișări.
descendenți mutanți.
Continuați de la al doilea pas.

Execuția este întreruptă fie când se găsește o soluție, fie după un număr dat de iterații [19] .

Aplicații

Nu se știe cu siguranță cine a fost primul care a dat formularea matematică a problemei rucsacului. Una dintre primele referiri la acesta poate fi găsită într-un articol al lui George Ballard Matthews[20] [21] din 1897. Studiul intens al acestei probleme a început după publicarea de către D. B. Dantzig în 1957 a cărții „ Engleză. Discrete Variable Extremum Problem » [22] , mai ales în anii 70-90 ai secolului XX, atât de către teoreticieni, cât și de către practicieni [2] . În multe privințe, interesul a fost cauzat de o formulare destul de simplă a problemei, un număr mare de varietăți și proprietăți ale acesteia și, în același timp, de complexitatea soluției lor. În 1972, această problemă a fost inclusă în lista de probleme NP-complete a lui M. Karp ( articolul în limba engleză „Reducibility Among Combinatorial Problems” ) [23] .

O interpretare vizuală a problemei rucsacului a dus la faptul că aceasta și-a găsit aplicație în diverse domenii ale cunoașterii: în matematică, informatică și, la intersecția acestor științe, în criptografie . Într-una din lucrările de lingvistică computațională [24] , se propune formularea problemei rezumarii automate a textelor , un caz special al căruia corespunde formulării problemei rucsacului.

Pe baza problemei rucsacului, a fost creat primul algoritm de criptare asimetrică . Ideea criptografiei cu cheie publică a fost prezentată pentru prima dată de Whitfield Diffie și Martin Hellman la Conferința Națională a Calculatoarelor din 1976 [25] [26] .

De asemenea, problema rucsacului poate servi drept model pentru un număr mare de probleme industriale [2] [27] :

Amplasarea mărfurilor într-un depozit cu o suprafață minimă.
Tăierea țesăturii - dintr-o bucată de material existentă, obțineți numărul maxim de modele de o anumită formă.
Calculul investiţiilor de capital optime .

Problema rucsacului în criptografie

În 1978, Ralph Merkle și Martin Hellman au dezvoltat primul algoritm pentru criptarea generalizată a cheilor publice , criptosistemul Merkle-Hellman , bazat pe problema rucsacului. Au publicat versiuni cu o singură etapă (în engleză cu repetare unică ) și cu mai multe etape (în engleză cu repetare multiplă ), iar algoritmul a putut fi folosit doar pentru criptare. Dar Adi Shamir l-a adaptat pentru utilizare în semnăturile digitale [28] .

Ulterior, au fost propuse și alte criptosisteme bazate pe problema rucsacului, dintre care unele sunt o modificare a criptosistemului Merkle-Hellman. Criptosisteme cunoscute [29] :

Rucsacul lui Graham - Shamira
Rucsac Goodman - Macauley
Rucsac Nakkasha - Pupa
Rucsacul lui Shor - Rivesta

Criptare cu problema rucsacului

Datorită faptului că problema generală a rucsacului nu poate fi rezolvată exact într-un timp rezonabil, poate fi folosită în probleme criptografice . Pentru a face acest lucru, cu un set de articole cunoscut public, vom reprezenta mesajul ca un set de articole transmise și vom trimite greutatea totală a acestora [28] .

Definiție. Un vector rucsac este un set ordonat de n articole, unde este greutatea celui de-al -lea articol [30] . $A=(a_{1},...,a_{n})$ $a_i$ $i$

Vectorul rucsac este o cheie publică . Pentru a cripta textul simplu, acesta este împărțit în blocuri cu lungimea de biți, fiecare bit determinând prezența unui articol în rucsac (de exemplu, textul simplu corespunde prezenței primelor patru din șase articole posibile în rucsac). Se crede că unul indică prezența unui articol în rucsac, iar zero indică absența acestuia [28] . $n$ $(111100)$

După aceea, greutatea totală a articolelor din rucsac pentru textul simplu dat este calculată și transmisă ca text cifrat [28] .

Un exemplu de criptare cu acest algoritm:

Să fie dat un vector rucsac cu lungime . $A=(3\ 4\ 6\ 7\ 10\ 11)$ $n=6$

text simplu	1 1 1 1 1 0	0 0 1 1 0 0	0 0 0 0 0 0	0 0 0 0 0 1
Lucruri în rucsac	3 4 6 7 10	6 7		unsprezece
Text cifrat	3 + 4 + 6 + 7 + 10 = 30	6 + 7 = 13	0	unsprezece

Note

↑ Silvano, 1990 , p. unu.
↑ 1 2 3 Silvano, 1990 , p. 2.
↑ 1 2 Kellerer, Pferschy, Pisinger, 2004 , p. 127.
↑ 1 2 Kellerer, Pferschy, Pisinger, 2004 , p. 147.
↑ Silvano, 1990 , p. 157.
↑ G. Gallo, P. L. Hammer, B. Simeone. Probleme de rucsac cuadratic // Studii de programare matematică. - 2009. - 24 februarie ( vol. 12 ). - P. 132-149 . — ISSN 0303-3929 . Arhivat din original pe 24 octombrie 2016.
↑ 1 2 Brettauer, Shetty, 2002 .
↑ Okulov, 2007 , pp. 92-93.
↑ Okulov, 2007 , pp. 101-105.
↑ 1 2 3 4 5 Martello S., Toth P. Probleme la rucsac: algoritmi și implementări pe computer . - John Wiley & Sons Ltd., 1990. - S. 29,50 . — 296 p. — ISBN 0-471-92420-2 .
↑ Burkov, Gorgidze, Lovetsky, 1974 , p. 225.
↑ 1 2 3 Romanovsky I.V. Algoritmi pentru rezolvarea problemelor extreme . - Nauka, 1977. - S. 252 -259. — 352 p.
↑ Stephen S. Skiena. Algoritmi. Ghid de dezvoltare. - al 2-lea. - Sankt Petersburg. : BHV-Petersburg, 2011. - S. 448-451. — 720 s. - ISBN 978-5-9775-0560-4 .
↑ 1 2 Novikov, 2001 , p. 12.
↑ 1 2 Kellerer, Pferschy, Pisinger, 2004 .
↑ Dantzig G. B. Discrete-Variable Extremum Problems // Oper . Res. - Institutul de Cercetare Operațională și Științe de Management , 1957. - Vol. 5, Iss. 2. - P. 266-288. - 23 p.m. — ISSN 0030-364X ; 1526-5463 - doi:10.1287/OPRE.5.2.266
↑ Ariel Kulik, Hadas Shachnai. Nu există EPTAS pentru rucsac bidimensional // Scrisori de procesare a informațiilor. — 31.07.2010. - T. 110 , nr. 16 . — S. 707–710 . - doi : 10.1016/j.ipl.2010.05.031 .
↑ D.I. Batishchev, E.A. Neimark, N.V. Starostin. Aplicarea algoritmilor genetici la rezolvarea problemelor de optimizare discretă . - 2007. - Nijni Novgorod. Arhivat pe 22 februarie 2016 la Wayback Machine
↑ 1 2 3 4 5 S. M. Avdoshin, A. A. Savelyeva. Criptanaliză: starea actuală și perspectivele de dezvoltare . - S. 38 . Arhivat din original pe 17 martie 2016. (Rusă)
↑ G.B. Mathews. Despre împărțirea numerelor (engleză) . - 1897. - P. 486-490.
↑ Kellerer, Pferschy, Pisinger, 2004 , p. 3.
↑ Kellerer, Pferschy, Pisinger, 2004 , p. 9.
↑ R. Karp. Reductibilitatea printre problemele combinatorii . — 1972.
↑ Riedhammer et al, 2008 , pp. 2436.
↑ Schnaer, 2002 , p. 19.2.
↑ Gabidulin, Kshevetsky, Kolybelnikov, 2011 .
↑ Burkov, Gorgidze, Lovetsky, 1974 , p. 217.
↑ 1 2 3 4 Schnaer, 2002 , p. 19.1.
↑ Kin Ming Lai. Criptosisteme de rucsac: trecutul și viitorul . — 2001. (Rusă)
↑ Salomaa, 1995 , p. 103.

Literatură

in rusa

Levitin A. V. Algoritmi. Introducere în dezvoltare și analiză - M . : Williams , 2006. - S. 160-163. — 576 p. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmi: constructie si analiza = Introduction to Algorithms. - al 2-lea. - M . : „Williams” , 2006. - S. 456-458. — ISBN 0-07-013151-1 .
Robert Sedgwick . Algoritmi fundamentali în C++. Părțile 1-4. Analiză. Structuri de date. Triere. Căutare = algoritmi în C++. Părțile 1-4. fundamentale. structuri de date. Triere. In cautarea. - al 3-lea. - Rusia, Sankt Petersburg: „DiaSoft” , 2002. - S. 688. - ISBN 5-93772-047-4 , 0-201-35088-2.
Burkov V. N. , Gorgidze I. A. , Lovetsky S. E. Probleme aplicate ale teoriei grafurilor / ed. A. Ya. Gorgidze - Tbilisi : Centrul de calcul al Academiei de Științe a URSS , 1974. - 231 p.
V. N. Burkov, D. A. Novikov. Elemente ale teoriei grafurilor . - 2001. - S. 28.
S. Okulov. Programare în algoritmi . - primul. — Binom. Laboratorul de cunoștințe, 2007. - P. 384. - ISBN 5-94774-010-9 .
B. Schneier. Criptografia aplicată. Protocoale, algoritmi, cod sursă în limbaj C = Criptografie aplicată. Protocoale, algoritmi și cod sursă în C. - al 2-lea. - Triumf, 2002. - 816 p. - 3000 de exemplare. - ISBN 5-89392-055-4 . Arhivat pe 18 decembrie 2018 la Wayback Machine
A. Salomaa. Public Key Cryptography = Public-Key Cryptography. - M . : Mir, 1995. - S. 102-150. - ISBN 5-03-001991-X. Arhivat pe 4 martie 2016 la Wayback Machine
N. Koblitz. Curs de teoria numerelor în criptografie. - al 2-lea. - M . : Editura Științifică TVP, 2001. - S. 254. - ISBN 5-85484-014-6 .
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Securitatea informației : manual - M .: MIPT , 2011. - 225 p. — ISBN 978-5-7417-0377-9
Osipyan V. O. Despre sistemul de securitate a informațiilor bazat pe problema rucsacului // Buletinul Universității Politehnice din Tomsk [Buletinul TPU]. - 2006. - T. 309 , nr 2 . - S. 209-212 .

în limba engleză

Silvano Martelo, Paolo Toth. Probleme la rucsac . - Marea Britanie: Wiley, 1990. - 306 p. — ISBN 0-471-92420-2 .
Kellerer H. , Pferschy U. , Pisinger D. Knapsack Problems (engleză) - Springer Science + Business Media , 2004. - 548 p. - ISBN 978-3-642-07311-3 - doi:10.1007/978-3-540-24777-7
K. Riedhammer, D. Gillick, B. Favre și D. Hakkani-Tür. Împachetarea rucsacului pentru rezumatul întâlnirii . — Brisbane Australia: Proc. Interspeech, Brisbane, Australia, 2008.
Brettauer K. M. , Shetty B. Problema neliniară a rucsacului – algoritmi și aplicații (engleză) // European Journal of Operational Research - Elsevier BV , 2002. - Vol. 138, Iss. 3. - P. 459-472. — ISSN 0377-2217 ; 1872-6860 - doi:10.1016/S0377-2217(01)00179-5

Link -uri

Bun venit la Rucsac
Problema rucsacului de Eric Grimsom John Guttag - MIT
Rucsac Soluții pentru probleme în multe limbi
Das Rucksack-Problem (problema rucsacului) (germană)

Problema rucsacului
Aplicații	Problemă la rucsac în criptografie Sarcina de tăiere
Criptosisteme bazate pe problema rucsacului	Merkla-Hellman Naccasha - Pupa Graham - Shamira
În plus	Lista sarcinilor despre rucsac

Probleme NP-complete
Problema de maximizare a stivuirii (ambalării)	Ambalare in containere ambalare bidimensională ambalare liniară ambalare după greutate ambalare după valoare Problema rucsacului
teoria grafurilor teoria multimelor	Problemă de acoperire a vârfurilor Faceți clic pe problemă Problema unei multimi (multimi) independente Setați problema acoperirii Problema lui Steiner Problema vânzătorului ambulant Problemă generalizată a vânzătorului ambulant
Probleme algoritmice	Problemă de satisfacție pentru formulele booleene (în formă normală conjunctivă)
Jocuri de logică și puzzle-uri	Etichete generalizate (joc în N 2 -1) cea mai scurta solutie problema Probleme ale căror soluții sunt aplicate în Tetris Problemă generalizată de Sudoku Problemă de umplere a pătratului latin Sarcina lui Kakuro
Clasele de dificultate Cercetare operațională Optimizare Optimizare combinatorie Matematică aplicată Teoria algoritmilor Programare dinamică 21 Problemă Karp NP-completă