A hátizsák probléma

A hátizsák probléma (a hátizsák probléma is ) egy NP-teljes kombinatorikus optimalizálási probléma . Nevét a végső célról kapta: minél több értékes dolgot tegyen egy hátizsákba, feltéve, hogy a hátizsák befogadóképessége korlátozott. A hátizsák-probléma különféle változataival találkozhatunk a közgazdaságtan , az alkalmazott matematika , a kriptográfia és a logisztika területén .

Általánosságban a probléma a következőképpen fogalmazható meg: egy adott " költség" és "súly" tulajdonságú tételkészletből ki kell választani egy olyan részhalmazt , amelynek összköltsége maximális, az össztömeg korlátozásának betartása mellett.

A probléma klasszikus megfogalmazása

Legyen egy objektumkészlet, amelyek mindegyikének két paramétere van - tömeg és érték. Van egy hátizsák is, bizonyos teherbírással. A feladat egy olyan hátizsák megépítése, amelyben a benne lévő tárgyak maximális értéket képviselnek, miközben a hátizsák össztömegére vonatkozó korlátot be kell tartani.

Matematikailag a probléma a következőképpen fogalmazódik meg: van rakomány. Minden egyes terhelésre meghatározzák annak tömegét és értékét . A hátizsákban lévő tárgyak összsúlyának korlátját a teherbírás határozza meg . Szükséges $n$ $én$ $w_{i}>0$ $v_{i}>0$ $i=1,2,...,n$ $W$

maximalizálni

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

korlátozásokkal és [1] .

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

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

A hátizsák-probléma változatai

A problémafelvetés számos általánosítást tesz lehetővé, attól függően, hogy milyen feltételekkel támasztják a hátizsákot, tárgyakat vagy azok választását. A legnépszerűbb fajták a következők:

Hátizsák 0-1 ( eng. 0-1 Hátizsák Probléma ) [2] : minden tételből legfeljebb egy példány.
Korlátozott hátizsák-probléma [3] : nem több, mint az egyes elemek adott számú példánya.
Unbounded Knapsack Probléma [3] : Az egyes elemek tetszőleges számú példánya.
Feleletválasztós hátizsák-probléma [ 4] : Az elemek csoportokra vannak osztva, és minden csoportból csak egy elemet kell kiválasztani.
Több hátizsák probléma [5] : Több hátizsák létezik, mindegyiknek megvan a maga maximális súlya. Minden elem tetszőleges hátizsákba tehető vagy balra is helyezhető.
Többdimenziós hátizsák - probléma : a súly helyett több különböző erőforrást is megadnak (például súly, térfogat és halmozási idő). Minden elem adott mennyiségű erőforrást költ el. A tételek egy részhalmazát úgy kell kiválasztani, hogy az egyes erőforrások összköltsége ne haladja meg az erre az erőforrásra vonatkozó maximumot, és egyben a tételek összértéke maximális legyen [4] .
Másodfokú hátizsák probléma : az összértéket egy nemnegatív határozott másodfokú forma adja meg [6] .

Nemlineáris hátizsák probléma

A hátizsák-probléma egyik legáltalánosabb változata a nemlineáris . A következőképpen fogalmazható meg:

Hagyja, hogy a vektor határozza meg a hátizsákban lévő egyes cikkek példányainak számát. Ekkor a probléma az, hogy megtaláljuk a függvény minimumát ${\displaystyle x=(x_{1},..,x_{n})\in \mathbb {R} ^{n))$

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

adott megkötéssel:

$g(x)\leq b$ .

A függvényeket folyamatosnak és differenciálhatónak tételezzük fel . egy egész állandó, a halmaz nem üres [7] . $f(x),g(x):\mathbb {R} ^{n}\jobbra \mathbb {R}$ $\mathbb {R} ^{n}$ $b$ $S$

Lineáris függvények esetén a probléma a halmaztól függően a klasszikus megfogalmazások egyikére redukálódik : $f(x),g(x)$ $S$

${\displaystyle S=\{0,1\}^{n))$ - hátizsák 0-1
$S=\mathbb {N_{0}} ^{n}$ - korlátlan számú hátizsák
$S=\{(x_{1},..,x_{n})\in \mathbb {N_{0}} ^{n}:x_{i}\leq c_{i}\}$ - korlátozott hátizsák

A funkciók megválasztásának szabadsága szélesebb körű feladatok megoldását tesz lehetővé, beleértve a termelő létesítmények megszervezését is $f(x),g(x)$ , a minták optimális eloszlása egy regionalizált mintában , vagy a négyzetes hátizsák probléma megoldása [7] .

A megoldás pontos módszerei

Mint fentebb említettük, a hátizsák probléma az NP-teljes osztályba tartozik, és eddig nem találtak rá olyan polinomiális algoritmust , amely ésszerű időn belül megoldaná. Ezért a hátizsák-probléma megoldása során választani kell a "nagy" hátizsákokra nem alkalmazható pontos algoritmusok és a közelítő algoritmusok közül, amelyek gyorsan működnek, de nem garantálják a probléma optimális megoldását.

Teljes felsorolás

Más diszkrét problémákhoz hasonlóan a hátizsákos probléma is megoldható az összes lehetséges megoldás kimerítő felsorolásával .

A probléma állapotának megfelelően vannak hátizsákba rakható tárgyak, és meg kell határozni a rakomány maximális költségét, amelynek súlya nem haladja meg a . $N$ $W$

Minden tételnél 2 lehetőség van: a tárgyat a hátizsákba helyezik, vagy a tárgyat nem a hátizsákba helyezik. Ekkor az összes lehetséges opció felsorolása időbonyolultságú , ami lehetővé teszi, hogy csak kis számú elemre használjuk [8] . Az objektumok számának növekedésével a probléma ezzel a módszerrel elfogadható időn belül megoldhatatlanná válik. $O(2^{N})$

Az ábra egy iterációs fát mutat három elemhez. Minden levél az elemek bizonyos részhalmazának felel meg. A fa összeállítása után meg kell találni a maximális értékű levelet azok közül, amelyek tömege nem haladja meg a [9] -et . $W$

Elágazás és kötés módszer

Az elágazó és kötött módszer a nyers erő módszer egy változata, azzal a különbséggel, hogy a nyers erőfa tudatosan nem optimális ágait kizárjuk. A brute force módszerhez hasonlóan ez is lehetővé teszi az optimális megoldás megtalálását, ezért a pontos algoritmusokhoz tartozik.

Az eredeti algoritmus, amelyet Peter Kolesar javasolt 1967-ben, azt javasolja, hogy az elemeket egységköltségük (az érték és a súly aránya) szerint rendezzék, és készítsenek egy nyers erőfát . Javulása abban rejlik, hogy az egyes csomópontokhoz tartozó fa felépítése során megbecsülik a megoldás értékének felső korlátját , és a fa építése csak a maximális becsléssel rendelkező csomópontra vonatkozik [10] . Amikor a maximális felső korlát a fa levelében van, az algoritmus befejezi a munkáját.

Az elágazás és a kötés azon képessége, hogy csökkentse az iterációk számát, nagymértékben függ a bemeneti adatoktól. Csak akkor célszerű használni, ha a tételek fajlagos értékei jelentősen eltérnek [11] .

Dinamikus programozási módszerek

A határtalan hátizsák probléma

Az elemek súlyának további megszorításával a hátizsák-probléma pszeudopolinomiális időben megoldható dinamikus programozási módszerekkel .

Legyen minden elem súlya pozitív egész szám. Ezután a probléma megoldásához ki kell számítani az optimális megoldásokat mindenre , ahol az adott teherbírás. Határozzuk meg a teherbírású hátizsákba elhelyezhető tárgyak maximális értékét . $w_{i}$ $w\in \mathbb {Z} :0\leq w\leq W$ $W$ $m[w]$ $w$

Rekurzív képleteket írhat : $m[w]$

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

ahol a -edik elem értéke és súlya van, és az üres halmazból származó maximumot nullának kell tekinteni. $v_{i},w_{i}$ $én$

Valójában az utolsó egyenlet R. Bellman funkcionális egyenlete vagy a dinamikus programozás funkcionális egyenlete. Ebben az esetben a megoldáshoz elegendő kiszámítani az összes értéket , kezdve a [12] -ig . Ha minden lépésnél eltárolunk egy olyan elemkészletet, amely a maximális értéket realizálja, akkor az algoritmus az optimális elemkészletet is megadja. $m[w]$ $0$ $W$

Mivel minden lépésben meg kell találni az elemek maximumát, az algoritmus számítási összetettsége . Mivel ez exponenciálisan függhet a bemenet méretétől, az algoritmus pszeudopolinomiális . Ezért ennek az algoritmusnak a hatékonyságát az értéke határozza meg . Az algoritmus kiváló eredményeket ad a -ra , de nem túl jót a [13] -ra . $n$ $O(nW)$ $W$ $W$ $W\leq 1000$ $W\geq 10\000\000$

Hátizsák probléma 0-1

A 0-1 hátizsák feladat megoldása közel áll az előző feladat megoldásához, de figyelembe kell venni, hogy minden tétel egy példányban van. Legyen az első rendelkezésre álló tételekből nyert tételek maximális értéke , amelyek össztömege nem haladja meg a . $m[i,w]$ $én$ $w$

Visszatérő kapcsolatok :

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

Kiszámolva megtalálhatja a pontos megoldást. Ha a tömb elfér a gép memóriájában, akkor valószínűleg ez az algoritmus az egyik leghatékonyabb [12] . $m[n,W]$ $m[i,w]$

// Bevitel: // Elemértékek (v tömbbe betöltve) // Tételsúlyok (w tömbbe betöltve) Tételek száma (n) Terhelhetőség (W) j esetén 0 - tól W - ig tegye : m [ 0 , j ] := 0 1 - től n - ig csinálom : j esetén 0 - tól W - ig tegye : ha w [ i ] > j , akkor : m [ i , j ] := m [ i -1 , j ] mást : m [ i , j ] := max ( m [ i -1 , j ], m [ i -1 , j - w [ i ]] + v [ i ])

A megoldást dinamikus programozással a következőképpen szemléltethetjük: egy kétdimenziós síkon az objektumok számát a tengely mentén , súlyukat pedig a tengely mentén ábrázoljuk. Az első lépésben a koordináták origójából két egyenest építünk: egy vízszintes, amely megfelel annak, hogy az első objektumot nem vettük fel, és egy ferde vonal, amely megfelel az első objektumnak. A tengelyre vetületük megegyezik a tárgy súlyával. A második lépésben ismét 2 vonal épül, vízszintes (a második objektumot nem vették fel) vagy ferde (a második objektumot vették). Állítsuk be a vízszintes ívek hosszát nullára, a ferde ívek hosszát pedig az objektum értékére [14] . Így a probléma bármely megoldása megfelel egy útvonalnak a felépített fában . A probléma a maximális hosszúságú út megtalálására redukálódik [14] . Hagyja, hogy a kapacitás a hátizsák . $x$ $Y$ $Y$ $W=14$

Cikkszám	Érték	A súlyt
egy	3	5
2	5	tíz
3	négy	6
négy	2	5

Az ábrán látható, hogy az optimális megoldás összértéke 7, mivel ez a maximális érték a megszerkesztett fában.

Dinamikus programozás a tételértékek felett

Az ismétlődési relációkat nemcsak az objektumok súlya, hanem az érték tekintetében is fel lehet írni. Ehhez a tételek minimális súlyát a teljes értékkel jelöljük, amelyet az első tételekből kaphatunk . Ha a kívánt súlyt nem lehet elérni, akkor jelölje meg . $y[i,V]$ $V$ $én$ $y[i,V]=W+1$

Ezt követően megoldjuk a funkcionális dinamikus programozási egyenletet :

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

kezdeti feltételekkel :

$y[0,0]=0$

$y[0,V]=W+1$ [tizenöt]

Hozzávetőleges megoldási módszerek

A legtöbb NP-teljes feladathoz hasonlóan nem mindig szükséges pontos megoldást találni, mivel az optimálishoz közeli megoldások alkalmazhatók az alkalmazott feladatokban.

Mohó algoritmus

A probléma mohó algoritmussal való megoldásához szükséges a dolgokat meghatározott értékük (vagyis egy tárgy értékének súlyához viszonyított aránya) szerint rendezni, és a legmagasabb fajlagos értékű tárgyakat elhelyezni a hátizsákban [10] .

Ennek az algoritmusnak a futási ideje a rendezési idő és a halmozási idő összege. A tételek rendezésének összetettsége . Ezután kiszámítja, hogy a teljes idő alatt hány elem fér el a hátizsákban [10] . Az ebből eredő bonyolultság , amikor a rendezésre van szükség, és amikor az adatok már rendezve vannak [10] . $O(N\log(N))$ $O(N)$ $O(N\log(N))$ $O(N)$

Példa . Hagyja, hogy a kapacitás a hátizsák . A tételek már egységérték szerint vannak rendezve. Használjuk a mohó algoritmust. $W=80$

én	a súlyt	ár	ár/súly
egy	tizenöt	60	négy
2	harminc	90	3
3	ötven	100	2

Az elsőt a hátizsákba tesszük, utána a másodikat. A harmadik elem nem fér be a hátizsákba. A hátizsákban lévő tárgyak összértéke 150. Ha a második és harmadik elemet vennénk, akkor az összérték 190 lenne. Így kaptunk néhány nem optimális megoldást.

Meg kell érteni, hogy egy mohó algoritmus az optimálistól tetszőlegesen távoli válaszhoz vezethet. Például, ha az egyik elem súlya 1 és költsége 2, a másik súlya pedig W és költsége W, akkor a mohó algoritmus 2-es összköltséget fog értékelni W optimális válasz mellett. ugyanakkor ugyanaz az algoritmus a korlátlan hátizsák-problémára az optimális érték legalább 50%-ának megfelelő választ ad [10] .

A mohó algoritmust először George Danzig [16] javasolta a korlátlan hátizsák probléma megoldására.

Hozzávetőleges séma teljesen polinomiális időhöz

Mivel a feladat polinomiális idejű megoldásának pontos algoritmusát nem sikerült megtalálni, felmerült a probléma, hogy garantált pontosságú polinomiális megoldást kapjunk . Ehhez számos közelítő séma létezik teljesen polinomiális időre , azaz olyan összetettséggel, amely polinom és -ben . $1-\varepsilon$ $n$ ${\frac {1}{\varepsilon }}$

A klasszikus séma mögött az az ötlet, hogy csökkentse a tételértékek megadásának pontosságát. Ha a hasonló értékű tételeket egy csoportba vonja össze, csökkentheti a különböző tételek számát. Az algoritmus a következőképpen van felírva [15] :

Keressünk hozzávetőleges megoldást egy mohó algoritmus segítségével. Legyen a pontos megoldás. Majd a mohó algoritmus hatékonysági becsléséből . ${\displaystyle x^{l))$ $x^{*}$ ${\displaystyle x^{l}\leq x^{*}\leq 2x^{l))$
Az értékeket a következőképpen skálázzuk: . $v'_{i}=\left\lfloor {\frac {v_{i}}{\frac {x^{l}\varepsilon }{n}}}\right\rfloor$
A dinamikus programozási algoritmus segítségével az objektumok egész értékeivel kapcsolatos problémára megoldást találunk.

Számos különböző közelítési séma létezik. Ezek azonban erősen függenek a hátizsák-probléma megfogalmazásától. Például, ha egy második egyenlőtlenségi típusú kényszer (kétdimenziós hátizsák) jelenik meg a feltételben, akkor a feladatnak már nincs ismert polinomiális idősémája [17] .

Genetikai algoritmusok

Más NP-nehéz optimalizálási problémákhoz hasonlóan a hátizsák-probléma megoldására genetikai algoritmusokat használnak . Nem garantálják az optimális megoldás megtalálását polinomiális időben , és nem adnak becslést a megoldás közelségéről az optimálishoz, de jó időmutatókkal rendelkeznek, lehetővé téve, hogy gyorsabban találjon egy meglehetősen jó megoldást, mint más ismert determinisztikus vagy heurisztikus . mód. [tizennyolc]

Minden egyed ( genotípus ) azoknak a tárgyaknak a részhalmaza, amelyeket a táskába szeretnénk csomagolni (tömegük meghaladhatja a megengedett teherbírást). A kényelem érdekében az információkat bináris karakterláncokként tároljuk, amelyekben minden bit meghatározza, hogy ez az elem belefér-e egy táskába [19] .

A fitnesz funkció határozza meg a megoldás közelségét az optimálishoz. Például a tételek összértéke szolgálhat ilyennek, feltéve, hogy a teljes tömeg nem haladja meg a teherbírást.

Egy sor generációváltás után, amelyben a legrátermettebb egyedeket keresztezik , a többit pedig figyelmen kívül hagyják, az algoritmusnak az eredeti megoldásokat kell javítania [19] .

A részhalmazösszeg feladat megoldása

A hátizsák 0-1 probléma speciális esete a részhalmazösszeg probléma . Legyen a hátizsák teherbírása, a -edik cikk súlya és költsége . Így a feladat az, hogy a hátizsákot a lehető legszorosabban töltse be, vagy teljesen kimerítse az erőforrásokat: $W$ $w_{i}$ $én$ $v_{i}=w_{i}$

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

A megoldáshoz használhatja az említett genetikai algoritmust . Az egyén vektor . Fitness funkcióként a tárgyak össztömegének közelségét kell használni a -hoz, az egyetlen tulajdonsággal, hogy a hátizsákba elférő készletek előnyösebbek (a tárgyak össztömege kisebb, mint ) [19] . $(x_{1},...,x_{n})$ $W$ $W$

Határozzuk meg formálisan a fitnesz függvényt . Legyen az összes elem súlyának összege. Ezután - a hátizsákban lévő tárgyak súlyának maximális lehetséges eltérése a -tól . $f(x_{1},..,x_{n}):\{0,1\}^{n}\jobbra \mathbb {R}$ $\mathcal{S}$ ${\textstyle \Delta _{max}=max(W,{\mathcal {S}}-W)}$ $W$

Legyen az adott vektor elemeinek összsúlya. Aztán feltesszük: ${\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]

Az általános algoritmus segítségével közelítő megoldást találhatunk:

Hozzon létre egy véletlenszerű egyedhalmazt - egy populációt.
Számítsa ki az adaptációs függvényt minden egyénre!
Csak a legrátermettebb egyedeket hagyja meg (természetes szelekció).
Végezzen kereszteket.
mutáló utód.
Folytassa a második lépéstől.

A végrehajtás vagy a megoldás megtalálásakor, vagy adott számú iteráció után megszakad [19] .

Alkalmazások

Nem tudni biztosan, hogy ki adta meg először a hátizsák-probléma matematikai megfogalmazását. Az egyik első utalás erre George Ballard Matthews cikkében található[20] [21] 1897-ben kelt. Ennek a problémának az intenzív tanulmányozása azután kezdődött, hogy D. B. Dantzig 1957-ben megjelent az „ English. Discrete Variable Extrémum Problem » [22] , különösen a XX. század 70-90-es éveiben, elméleti szakemberek és gyakorlati szakemberek által [2] . Az érdeklődést sok tekintetben a probléma meglehetősen egyszerű megfogalmazása, számos változata és tulajdonsága, és egyben megoldásuk összetettsége váltotta ki. 1972-ben ez a probléma felkerült M. Karp NP-teljes problémák listájára ( "Reducibility among Combinatorial Problems" angol cikk) [23] .

A hátizsák-probléma vizuális értelmezése oda vezetett, hogy a különböző tudásterületeken alkalmazásra talált: a matematikában, a számítástechnikában és e tudományok metszéspontjában a kriptográfiában is . Az egyik számítógépes nyelvészeti munkában [24] a szövegek automatikus összegzésének problémájának megfogalmazását javasolják , amelynek egy speciális esete a hátizsák-probléma megfogalmazásának felel meg.

A hátizsák-probléma alapján elkészült az első aszimmetrikus titkosítási algoritmus . A nyilvános kulcsú kriptográfia ötletét először Whitfield Diffie és Martin Hellman mutatta be az 1976 -os Országos Számítógépes Konferencián [25] [26] .

Ezenkívül a hátizsák-probléma számos ipari probléma modelljeként szolgálhat [2] [27] :

Áruk elhelyezése minimális területű raktárban.
Szövetvágás - egy meglévő anyagból szerezze be a maximális számú mintát egy adott alakúra.
Optimális tőkebefektetések számítása .

A hátizsák probléma a kriptográfiában

1978-ban Ralph Merkle és Martin Hellman kifejlesztette az általános nyilvános kulcsú titkosítás első algoritmusát , a Merkle-Hellman kriptorendszert a hátizsák - probléma alapján. Egylépcsős ( angolul singly-iterated ) és többlépcsős ( angol multiply-iterated ) változatot adtak ki, és az algoritmus csak titkosításra volt használható. De Adi Shamir adaptálta digitális aláírásokhoz [28] .

Ezt követően más, a hátizsák-problémán alapuló kriptorendszereket javasoltak, amelyek közül néhány a Merkle-Hellman kriptorendszer módosítása. Ismert titkosítási rendszerek [29] :

Graham hátizsákja - Shamira
Goodman hátizsák - Macauley
Nakkasha hátizsák - Stern
Shor hátizsák - Rivesta

Titkosítás a hátizsák problémájával

Tekintettel arra, hogy az általános hátizsák probléma nem oldható meg pontosan ésszerű időn belül, kriptográfiai problémákban használható. Ehhez egy nyilvánosan ismert elemkészlettel az üzenetet továbbított elemek halmazaként jelenítjük meg, és elküldjük a teljes súlyukat [28] .

Meghatározás. A hátizsák vektor n elemből álló rendezett halmaz, ahol a -edik elem súlya [30] . $A=(a_{1},...,a_{n})$ $a_i$ $én$

A hátizsák vektor egy nyilvános kulcs . Az egyszerű szöveg titkosításához azt bithosszúságú blokkokra bontják , ahol minden bit meghatározza egy-egy elem jelenlétét a hátizsákban (például a sima szöveg a hat lehetséges elem közül az első négynek felel meg a hátizsákban). Úgy tartják, hogy az egyes egy tárgy jelenlétét jelzi a hátizsákban, a nulla pedig a hiányát [28] . $n$ $(111100)$

Ezt követően a rendszer kiszámítja a hátizsákban lévő tárgyak összsúlyát az adott nyílt szöveghez, és titkosított szövegként továbbítja [28] .

Példa a titkosításra ezzel az algoritmussal:

Legyen adott egy hosszúságú hátizsák vektor . $A=(3\4\6\7\10\11)$ $n=6$

egyszerű szöveg	1 1 1 1 1 0	0 0 1 1 0 0	0 0 0 0 0 0	0 0 0 0 0 1
Dolgok a hátizsákban	3 4 6 7 10	6 7		tizenegy
Rejtjelezett szöveg	3 + 4 + 6 + 7 + 10 = 30	6 + 7 = 13	0	tizenegy

Jegyzetek

↑ Silvano, 1990 , p. egy.
↑ 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. Kvadratikus hátizsák problémák // Mathematical Programming Studies. - 2009. - február 24. ( 12. köt. ). - 132-149 . o . — ISSN 0303-3929 . Archiválva az eredetiből 2016. október 24-én.
↑ 1 2 Brettauer, Shetty, 2002 .
↑ Okulov, 2007 , pp. 92-93.
↑ Okulov, 2007 , pp. 101-105.
↑ 1 2 3 4 5 Martello S., Toth P. Hátizsákproblémák: algoritmusok és számítógépes implementációk . - 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. Algoritmusok extrém problémák megoldására . - Nauka, 1977. - S. 252 -259. — 352 p.
↑ Stephen S. Skiena. Algoritmusok. Fejlesztési útmutató. - 2. - Szentpétervár. : 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 Extrémum Problems // Oper . Res. - Operációkutató és Vezetéstudományi Intézet , 1957. - 1. évf. 5, Iss. 2. - P. 266-288. - 23 óra — ISSN 0030-364X ; 1526-5463 - doi:10.1287/OPRE.5.2.266
↑ Ariel Kulik, Hadas Shachnai. Kétdimenziós hátizsákhoz nincs EPTAS // Information Processing Letters. — 2010-07-31. - T. 110 , sz. 16 . – S. 707–710 . - doi : 10.1016/j.ipl.2010.05.031 .
↑ D.I. Batishchev, E.A. Neimark, N.V. Starostin. Genetikai algoritmusok alkalmazása diszkrét optimalizálási problémák megoldására . - 2007. - Nyizsnyij Novgorod. Archiválva : 2016. február 22. a Wayback Machine -nél
↑ 1 2 3 4 5 S. M. Avdoshin, A. A. Saveljeva. Kriptanalízis: jelenlegi állapot és fejlődési kilátások . - S. 38 . Az eredetiből archiválva : 2016. március 17. (Orosz)
↑ G.B. Mathews. A számok felosztásáról (angol) . - 1897. - P. 486-490.
↑ Kellerer, Pferschy, Pisinger, 2004 , p. 3.
↑ Kellerer, Pferschy, Pisinger, 2004 , p. 9.
↑ R. Karp. Redukálhatóság a kombinatorikus problémák között . – 1972.
↑ Riedhammer et al, 2008 , pp. 2436.
↑ Schnaer, 2002 , p. 19.2.
↑ Gabidulin, Ksevetszkij, Kolybelnikov, 2011 .
↑ Burkov, Gorgidze, Lovetsky, 1974 , p. 217.
↑ 1 2 3 4 Schnaer, 2002 , p. 19.1.
↑ Kin Ming Lai. Knapsack Cryptosystems: A múlt és a jövő . – 2001. (Orosz)
↑ Salomaa, 1995 , p. 103.

Irodalom

oroszul

Levitin A. V. Algoritmusok. Bevezetés a fejlesztésbe és elemzésbe - 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. Algoritmusok: felépítés és elemzés = Introduction to Algorithms. - 2. - M . : "Williams" , 2006. - S. 456-458. — ISBN 0-07-013151-1 .
Robert Sedgwick . Alapvető algoritmusok C++ nyelven. rész 1-4. Elemzés. Adatstruktúrák. Válogató. Keresés = Algoritmusok C++ nyelven. rész 1-4. alapok. adatstruktúrák. Válogató. Keresés. - 3. - Oroszország, Szentpétervár: "DiaSoft" , 2002. - S. 688. - ISBN 5-93772-047-4 , 0-201-35088-2.
Burkov V. N. , Gorgidze I. A. , Lovetsky S. E. A gráfelmélet alkalmazott problémái / szerk. A. Ya. Gorgidze - Tbiliszi : A Szovjetunió Tudományos Akadémia Számítástechnikai Központja , 1974. - 231 p.
V. N. Burkov, D. A. Novikov. A gráfelmélet elemei . - 2001. - S. 28.
S. Okulov. Programozás algoritmusokban . - 1. — Binom. Tudáslaboratórium , 2007. - P. 384. - ISBN 5-94774-010-9 .
B. Schneier. Alkalmazott kriptográfia. Protokollok, algoritmusok, forráskód C nyelven = Applied Cryptography. Protokollok, algoritmusok és forráskód a C. - 2nd. - Triumph, 2002. - 816 p. - 3000 példányban. - ISBN 5-89392-055-4 . Archiválva : 2018. december 18. a Wayback Machine -nál
A. Salomaa. Nyilvános kulcsú titkosítás = Public Key Cryptography. - M . : Mir, 1995. - S. 102-150. - ISBN 5-03-001991-X. Archiválva : 2016. március 4. a Wayback Machine -nál
N. Koblitz. Számelméleti kurzus titkosírásból. - 2. - M . : TVP Tudományos Kiadó, 2001. - S. 254. - ISBN 5-85484-014-6 .
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Információbiztonság : tankönyv - M .: MIPT , 2011. - 225 p. — ISBN 978-5-7417-0377-9
Osipyan V. O. A hátizsák-problémán alapuló információbiztonsági rendszerről // A Tomszki Politechnikai Egyetem közleménye [TPU Bulletin]. - 2006. - T. 309 , 2. sz . - S. 209-212 .

angolul

Silvano Martelo, Paolo Toth. Hátizsák problémák . - Nagy-Britannia: Wiley, 1990. - 306 p. — ISBN 0-471-92420-2 .
Kellerer H. , Pferschy U. , Pisinger D. Hátizsák problémák (angol) - 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 és D. Hakkani-Tür. A találkozó összefoglaló hátizsákjának bepakolása . – Brisbane Ausztrália: Proc. Interspeech, Brisbane, Ausztrália, 2008.
Brettauer K. M. , Shetty B. A nemlineáris hátizsák probléma – algoritmusok és alkalmazások (angol) // 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

Linkek

Üdvözöljük a hátizsákban
Hátizsákprobléma – Eric Grimsom, John Guttag – MIT
Hátizsák Problémamegoldások sok nyelven
Das Rucksack-Problem (hátizsák probléma) (német)

A hátizsák probléma
Alkalmazások	Hátizsák probléma a kriptográfiában Vágási feladat
A hátizsák problémán alapuló kriptorendszerek	Merkla-Hellman Naccasha – Stern Graham – Shamira
Továbbá	A hátizsákkal kapcsolatos feladatok listája

NP-teljes problémák
A halmozás (csomagolás) maximalizálási problémája	Csomagolás konténerekbe kétdimenziós csomagolás lineáris csomagolás súly szerinti csomagolás érték szerinti csomagolás A hátizsák probléma
gráfelmélet halmazelmélet	Csúcsborítási probléma Kattintson a probléma Egy független halmaz (halmaz) problémája Állítsa be a fedési problémát Steiner probléma Az utazó eladó probléma Általános utazó eladó probléma
Algoritmikus problémák	Kielégíthetőségi probléma Boole-képleteknél (konjunktív normál formában)
Logikai játékok és rejtvények	Általános címkék (játék N 2 -1-ben) legrövidebb megoldási probléma Problémák, amelyek megoldásait a Tetrisben alkalmazzák Általános Sudoku probléma Latin négyzet kitöltési probléma Kakuro feladata
Nehézségi osztályok Operációkutatás Optimalizálás Kombinatorikus optimalizálás Alkalmazott matematika Algoritmusok elmélete Dinamikus programozás 21 NP-teljes Karp probléma