Problém s batohem

Problém batohu (také problém batohu ) je NP-úplný kombinatorický optimalizační problém . Svůj název dostal podle konečného cíle: dát do batohu co nejvíce cenných věcí za předpokladu, že kapacita batohu je omezená. S různými variacemi problému batohu se můžeme setkat v ekonomice , aplikované matematice , kryptografii a logistice .

Obecně lze problém formulovat následovně: z dané množiny položek s vlastnostmi „cena“ a „hmotnost“ je třeba vybrat podmnožinu s maximálními celkovými náklady při dodržení omezení celkové hmotnosti.

Klasické vyjádření problému

Nechť existuje množina objektů, z nichž každý má dva parametry – hmotnost a hodnotu. Nechybí ani batoh s určitou nosností. Úkolem je postavit batoh s maximální hodnotou předmětů uvnitř, při respektování limitu batohu na celkovou hmotnost.

Matematicky je problém formulován následovně: existuje náklad. Pro každé zatížení se určí jeho hmotnost a hodnota . Limit celkové hmotnosti věcí v batohu je dán nosností . Nutné $n$ $i$ $w_{i}>0$ $v_{i}>0$ $i=1,2,...,n$ $W$

maximalizovat

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

s omezeními a [1] .

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

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

Varianty problému batohu

Problémové prohlášení umožňuje velké množství zobecnění v závislosti na podmínkách kladených na batoh, předměty nebo jejich volbu. Nejoblíbenější odrůdy jsou následující:

Batoh 0-1 ( eng. 0-1 Knapsack Problem ) [2] : ne více než jedna kopie každé položky.
Problém s omezeným batohem [3] : ne více než daný počet výskytů každé položky.
Neohraničený problém batohu [3] : Libovolný počet instancí každé položky.
Problém batohu s více možnostmi [ 4] : Položky jsou rozděleny do skupin a z každé skupiny je třeba vybrat pouze jednu položku.
Problém s více batohy [5] : Existuje několik batohů, z nichž každý má svou vlastní maximální hmotnost. Každou položku lze vložit do jakéhokoli batohu nebo ponechat.
Problém vícerozměrného batohu : místo hmotnosti je uvedeno několik různých zdrojů (například hmotnost, objem a doba stohování). Každá položka utratí danou částku z každého zdroje. Je nutné zvolit podmnožinu položek tak, aby celková cena každého zdroje nepřesáhla maximum pro tento zdroj a zároveň celková hodnota položek byla maximální [4] .
Kvadratický problém batohu : celková hodnota je dána nezápornou definitní kvadratickou formou [6] .

Problém nelineárního batohu

Jedna z nejobecnějších variant problému batohu je nelineární . Lze jej formulovat následovně:

Nechte vektor určit počet výskytů každé položky v batohu. Pak je problém najít minimum funkce ${\displaystyle x=(x_{1},..,x_{n})\in \mathbb {R} ^{n))$

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

s daným omezením:

$g(x)\leq b$ .

Předpokládá se, že funkce jsou spojité a diferencovatelné na . je celočíselná konstanta, množina je neprázdná [7] . $f(x),g(x):\mathbb {R} ^{n}\rightarrow \mathbb {R}$ $\mathbb {R} ^{n}$ $b$ $S$

V případě lineárních funkcí je problém redukován na jednu z klasických formulací v závislosti na množině : $f(x),g(x)$ $S$

${\displaystyle S=\{0,1\}^{n))$ - batoh 0-1
$S=\mathbb {N_{0}} ^{n}$ - neomezený batoh
$S=\{(x_{1},..,x_{n})\in \mathbb {N_{0}} ^{n}:x_{i}\leq c_{i}\}$ - limitovaný batoh

Volnost ve výběru funkcí umožňuje řešit širší třídu úkolů, včetně organizace výrobních zařízení $f(x),g(x)$ , optimální rozložení vzorků v regionalizovaném vzorku nebo řešení problému kvadratického batohu [7] .

Přesné metody řešení

Jak již bylo zmíněno výše, problém batohu patří do třídy NP-complete a zatím pro něj nebyl nalezen žádný polynomiální algoritmus , který by jej vyřešil v rozumném čase. Při řešení problému s batohem je proto nutné volit mezi přesnými algoritmy, které nejsou použitelné pro „velké“ batohy, a přibližnými, které fungují rychle, ale nezaručují optimální řešení problému.

Úplný výčet

Stejně jako u jiných diskrétních problémů lze problém s batohem vyřešit vyčerpávajícím výčtem všech možných řešení.

Podle stavu problému existují položky, které lze vložit do batohu, a je třeba určit maximální náklady na náklad, jehož hmotnost nepřesahuje . $N$ $W$

Pro každý předmět jsou 2 možnosti: předmět je umístěn v batohu, nebo předmět není umístěn v batohu. Pak má výčet všech možných možností časovou složitost , což umožňuje jeho použití jen pro malý počet položek [8] . S nárůstem počtu objektů se problém stává touto metodou v přijatelném čase neřešitelný. $O(2^{N})$

Obrázek ukazuje iterační strom pro tři položky. Každý list odpovídá nějaké podmnožině položek. Po sestavení stromu je nutné najít list s maximální hodnotou mezi těmi, jejichž hmotnost nepřesahuje [9] . $W$

Metoda větvení a vazby

Metoda větví a vázaných je variací metody hrubé síly s tím rozdílem, že jsou vyloučeny vědomě neoptimální větve stromu hrubé síly. Stejně jako metoda hrubé síly umožňuje najít optimální řešení a patří tedy k přesným algoritmům.

Původní algoritmus, navržený Peterem Kolesarem v roce 1967, navrhuje třídit položky podle jejich jednotkové ceny (poměr hodnoty k hmotnosti) a sestavit strom hrubé síly . Jeho vylepšení spočívá v tom, že v procesu budování stromu pro každý uzel je odhadnuta horní mez hodnoty řešení a konstrukce stromu pokračuje pouze pro uzel s maximálním odhadem [10] . Když je maximální horní mez v listu stromu, algoritmus ukončí svou práci.

Schopnost větvení a vazby snížit počet iterací do značné míry závisí na vstupních datech. Je vhodné jej použít pouze v případě, že se konkrétní hodnoty položek výrazně liší [11] .

Metody dynamického programování

Neohraničený problém batohu

S dodatečným omezením na hmotnosti položek lze problém batohu vyřešit v pseudopolynomiálním čase pomocí metod dynamického programování .

Váha každé položky nechť je kladné celé číslo. Poté je pro vyřešení problému nutné vypočítat optimální řešení pro všechny , kde je daná nosnost. Definujme jako maximální hodnotu předmětů, které lze umístit do batohu s nosností . $w_{i}$ $w\in \mathbb {Z} :0\leq w\leq W$ $W$ $m[w]$ $w$

Pro můžete psát rekurzivní vzorce : $m[w]$

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

kde je hodnota a váha -té položky a maximum z prázdné množiny by mělo být považováno za rovné nule. $v_{i},w_{i}$ $i$

Ve skutečnosti je poslední rovnicí funkcionální rovnice R. Bellmana neboli funkcionální rovnice dynamického programování. V tomto případě k vyřešení stačí vypočítat všechny hodnoty , počínaje a až [12] . Pokud navíc v každém kroku uložíme sadu položek, která realizuje maximální hodnotu, pak algoritmus také poskytne optimální sadu položek. $m[w]$ $0$ $W$

Protože v každém kroku je nutné najít maximum položek, má algoritmus výpočetní náročnost . Protože může exponenciálně záviset na velikosti vstupu, je algoritmus pseudopolynomiální . Proto je účinnost tohoto algoritmu určena hodnotou . Algoritmus dává vynikající výsledky pro , ale ne příliš dobré pro [13] . $n$ $O(nW)$ $W$ $W$ $W\leq 1000$ $W\geq 10\000\000$

Problém batohu 0-1

Řešení úlohy batohu 0-1 se blíží řešení předchozí úlohy, je však nutné počítat s tím, že každá položka je v jediném exempláři. Dovolit je maximální hodnota položek získaných z prvních dostupných položek s celkovou hmotností nepřesahující . $m[i,w]$ $i$ $w$

Opakující se vztahy :

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

Výpočtem můžete najít přesné řešení. Pokud se pole vejde do paměti stroje, pak je tento algoritmus pravděpodobně jedním z nejúčinnějších [12] . $m[n,W]$ $m[i,w]$

// Vstup: // Hodnoty položek (načteny do pole v) // Hmotnosti položek (načtené do pole w) // Počet položek (n) // Nosnost (W) pro j od 0 do W proveďte : m [ 0 , j ] := 0 pro já od 1 do n udělám : pro j od 0 do W proveďte : pokud w [ i ] > j pak : m [ i , j ] := m [ i -1 , j ] jinak : m [ i , j ] := max ( m [ i -1 , j ], m [ i -1 , j - w [ i ]] + v [ i ])

Řešení lze znázornit pomocí dynamického programování následovně: na dvourozměrné rovině je počet objektů vykreslen podél osy a jejich hmotnost je vynesena podél osy. V prvním kroku se z počátku souřadnic sestaví dvě čáry: vodorovná, která odpovídá skutečnosti, že první objekt nebyl pořízen, a nakloněná, která odpovídá prvnímu pořízenému objektu. Jejich průměty na osu se rovnají váze předmětu. Ve druhém kroku se opět postaví 2 čáry, horizontální (druhý objekt nebyl pořízen) nebo šikmý (druhý objekt byl pořízen). Délku vodorovných oblouků nastavíme na nulu a délku šikmých oblouků na hodnotu objektu [14] . Jakékoli řešení problému tedy odpovídá nějaké cestě v konstruovaném stromu . Problém se redukuje na nalezení cesty maximální délky [14] . Nechte kapacitu batohu . $X$ $Y$ $Y$ $W=14$

Číslo položky	Hodnota	Váha
jeden	3	5
2	5	deset
3	čtyři	6
čtyři	2	5

Z obrázku je vidět, že celková hodnota pro optimální řešení je 7, protože se jedná o maximální hodnotu ve zkonstruovaném stromu.

Dynamické programování nad hodnotami položek

Rekurentní vztahy lze psát nejen s ohledem na váhu předmětů, ale také s ohledem na hodnotu. K tomu označíme minimální váhu položek celkovou hodnotou , kterou lze získat z prvních položek. Pokud požadovanou hmotnost nelze získat, označte ji jako . $y[i,V]$ $PROTI$ $i$ $y[i,V]=W+1$

Poté vyřešíme rovnici funkcionálního dynamického programování :

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

s počátečními podmínkami :

$y[0,0]=0$

$y[0,V]=W+1$ [patnáct]

Přibližné metody řešení

Stejně jako u většiny NP-úplných problémů není vždy nutné získat přesné řešení, protože řešení, která jsou blízká optimální, lze použít v aplikovaných problémech.

Greedy algoritmus

K vyřešení problému s chamtivým algoritmem je nutné seřadit věci podle jejich konkrétní hodnoty (tedy poměru hodnoty předmětu k jeho váze) a do batohu umístit předměty s nejvyšší specifickou hodnotou [10] .

Doba běhu tohoto algoritmu je součtem doby třídění a doby skládání. Složitost řazení položek je . Dále spočítá, kolik věcí se do batohu vejde za celkový čas [10] . Výsledná složitost při řazení je potřeba a když jsou data již setříděna [10] . $O(N\log(N))$ $O(N)$ $O(N\log(N))$ $O(N)$

Příklad . Nechte kapacitu batohu . Položky jsou již seřazeny podle hodnoty jednotky. Použijme chamtivý algoritmus. $W=80$

i	váha	cena	cena/váha
jeden	patnáct	60	čtyři
2	třicet	90	3
3	padesáti	100	2

Do batohu vložíme první položku a po ní druhou. Třetí položka se do batohu nevejde. Celková hodnota věcí v batohu je 150. Pokud by se vzal druhý a třetí předmět, celková hodnota by byla 190. Tím jsme získali nějaké neoptimální řešení.

Mělo by být zřejmé, že chamtivý algoritmus může vést k odpovědi libovolně vzdálené od optimální. Pokud má například jedna položka váhu 1 a cenu 2 a druhá má váhu W a cenu W, pak chamtivý algoritmus získá celkové náklady 2 s optimální odpovědí W. stejný algoritmus pro neohraničený problém batohu zároveň povede k odpovědi alespoň 50 % hodnoty optima [10] .

Chamtivý algoritmus poprvé navrhl George Danzig [16] pro řešení neomezeného problému batohu.

Přibližné schéma pro plně polynomiální čas

Protože nebyl nalezen přesný algoritmus pro řešení úlohy v polynomiálním čase , vyvstal problém získat polynomické řešení se zaručenou přesností . K tomu existuje řada přibližných schémat plně polynomiálního času , tedy se složitostí, která je polynomem v a . $1-\varepsilon$ $n$ ${\frac {1}{\varepsilon }}$

Myšlenkou klasického schématu je snížit přesnost uvádění hodnot položek. Spojením položek podobné hodnoty do jedné skupiny můžete snížit počet různých položek. Algoritmus je napsán následovně [15] :

Pojďme najít přibližné řešení pomocí chamtivého algoritmu. Nechť je přesné řešení. Potom z odhadu účinnosti chamtivého algoritmu . ${\displaystyle x^{l))$ $x^{*}$ ${\displaystyle x^{l}\leq x^{*}\leq 2x^{l))$
Měřte hodnoty takto: . $v'_{i}=\left\lpatro {\frac {v_{i}}{\frac {x^{l}\varepsilon }{n}}}\right\rfloor$
Pomocí dynamického programovacího algoritmu pro problém s celočíselnými hodnotami objektů najdeme řešení.

Existuje mnoho různých aproximačních schémat. Silně však závisí na formulaci problému batohu. Pokud se například v podmínce objeví druhé omezení typu nerovnosti (dvourozměrný batoh), pak problém již nemá známé polynomiální časové schéma [17] .

Genetické algoritmy

Stejně jako u jiných NP-tvrdých optimalizačních problémů se k řešení problému s batohem používají genetické algoritmy . Nezaručují nalezení optimálního řešení v polynomiálním čase a neposkytují odhad blízkosti řešení k optimálnímu, ale mají dobré časové ukazatele, které umožňují najít poměrně dobré řešení rychleji než jiné známé deterministické nebo heuristické metody. [osmnáct]

Každý jedinec ( genotyp ) je podmnožinou věcí, které chceme do brašny zabalit (jejich celková hmotnost může přesáhnout povolenou nosnost). Pro usnadnění jsou informace uloženy jako binární řetězce, ve kterých každý bit určuje, zda se tato položka vejde do brašny [19] .

Fitness funkce určuje blízkost řešení k optimálnímu. Jako taková může sloužit například celková hodnota položek za předpokladu, že celková hmotnost nepřesáhne nosnost.

Po sérii generačních změn, při kterých se kříží nejschopnější jedinci a zbytek se ignoruje, má algoritmus zlepšit původní řešení [19] .

Řešení problému součtu podmnožiny

Speciálním případem problému batohu 0-1 je problém součtu podmnožiny . Nechť je nosnost batohu, váha -té položky a její cena . Úkolem je tedy naložit batoh co nejtěsněji nebo zcela vyčerpat zdroje: $W$ $w_{i}$ $i$ $v_{i}=w_{i}$

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

K jeho vyřešení můžete použít zmíněný genetický algoritmus . Jednotlivec je vektor . Jako fitness funkci by se mělo používat blízkost celkové hmotnosti předmětů k , přičemž jedinou vlastností je, že sady, které se vejdou do batohu, jsou výhodnější (celková hmotnost předmětů je menší než ) [19] . $(x_{1},..,x_{n})$ $W$ $W$

Pojďme formálně definovat funkci fitness . Nechť je součet vah všech položek. Potom - maximální možná odchylka hmotnosti předmětů v batohu od . $f(x_{1},..,x_{n}):\{0,1\}^{n}\rightarrow \mathbb {R}$ $\mathcal{S}$ ${\textstyle \Delta _{max}=max(W,{\mathcal {S}}-W)}$ $W$

Nechť je celková váha položek pro daný vektor. Poté vložíme: ${\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]

Pomocí obecného algoritmu můžeme najít přibližné řešení:

Vytvořte náhodný soubor jedinců – populaci.
Vypočítejte adaptační funkci pro každého jednotlivce.
Ponechte pouze nejzdatnější jedince (přirozený výběr).
Proveďte kříže.
mutovat potomstvo.
Pokračujte od druhého kroku.

Provádění se přeruší buď při nalezení řešení, nebo po daném počtu iterací [19] .

Aplikace

Není jisté, kdo byl první, kdo dal matematickou formulaci problému s batohem. Jednu z prvních zmínek o ní lze nalézt v článku George Ballarda Matthewse[20] [21] z roku 1897. Intenzivní studium tohoto problému začalo po vydání knihy D. B. Dantziga v roce 1957 „ Angličtina. Extrémní problém diskrétních proměnných » [22] , zejména v 70.–90. letech 20. století, jak teoretiky, tak praktiky [2] . Zájem v mnoha ohledech vyvolala poměrně jednoduchá formulace problému, velké množství jeho odrůd a vlastností a zároveň složitost jejich řešení. V roce 1972 byl tento problém zařazen do seznamu NP-úplných problémů M. Karpa ( anglický článek "Reducibility Among Combinatorial Problems" ) [23] .

Vizuální interpretace problému batohu vedla k tomu, že našel uplatnění v různých oblastech poznání: v matematice, informatice a na průsečíku těchto věd v kryptografii . V jedné z prací o počítačové lingvistice [24] je navržena formulace problému automatické sumarizace textů , jehož speciální případ odpovídá formulaci problému batohu.

Na základě problému s batohem byl vytvořen první asymetrický šifrovací algoritmus . Myšlenku kryptografie s veřejným klíčem poprvé představili Whitfield Diffie a Martin Hellman na National Computer Conference v roce 1976 [25] [26] .

Problém batohu může také sloužit jako model pro velké množství průmyslových problémů [2] [27] :

Umístění zboží ve skladu s minimální plochou.
Řezání látky - z existujícího kusu materiálu získáte maximální počet vzorů určitého tvaru.
Výpočet optimálních kapitálových investic .

Problém batohu v kryptografii

V roce 1978 Ralph Merkle a Martin Hellman vyvinuli první algoritmus pro zobecněné šifrování veřejného klíče , kryptosystém Merkle-Hellman , založený na problému batohu. Vydali jednostupňové ( anglicky singly-iterated ) a vícestupňové ( anglicky multiply-iterated ) verze a algoritmus mohl být použit pouze pro šifrování. Ale Adi Shamir jej upravil pro použití v digitálních podpisech [28] .

Následně byly navrženy další kryptosystémy založené na problému batohu, z nichž některé jsou modifikací kryptosystému Merkle-Hellman. Známé kryptosystémy [29] :

Grahamův batoh - Shamira
Batoh Goodman - Macauley
Batoh Nakkasha - záď
Batoh Shor - Rivesta

Šifrování s problémem batohu

Vzhledem k tomu, že obecný problém batohu nelze vyřešit přesně v rozumném čase, lze jej použít v kryptografických problémech. Za tímto účelem s veřejně známou sadou položek budeme reprezentovat zprávu jako sadu přenášených položek a zašleme jejich celkovou váhu [28] .

Definice. Vektor batohu je uspořádaná množina n položek, kde je hmotnost -té položky [30] . $A=(a_{1},...,a_{n})$ $a_i$ $i$

Vektor batohu je veřejný klíč . Pro zašifrování otevřeného textu se rozdělí na bloky o bitové délce, přičemž každý bit určuje přítomnost předmětu v batohu (otevřený text například odpovídá přítomnosti prvních čtyř ze šesti možných předmětů v batohu). Předpokládá se, že jednička označuje přítomnost předmětu v batohu a nula jeho nepřítomnost [28] . $n$ $(111100)$

Poté se vypočítá celková váha předmětů v batohu pro daný otevřený text a přenese se jako šifrovaný text [28] .

Příklad šifrování pomocí tohoto algoritmu:

Nechť je dán batohový vektor s délkou . $A=(3\ 4\ 6\ 7\ 10\ 11)$ $n=6$

prostý text	1 1 1 1 1 0	0 0 1 1 0 0	0 0 0 0 0 0	0 0 0 0 0 1
Věci v batohu	3 4 6 7 10	6 7		jedenáct
Šifrovaný text	3 + 4 + 6 + 7 + 10 = 30	6 + 7 = 13	0	jedenáct

Poznámky

↑ Silvano, 1990 , str. jeden.
↑ 1 2 3 Silvano, 1990 , str. 2.
↑ 1 2 Kellerer, Pferschy, Pisinger, 2004 , str. 127.
↑ 1 2 Kellerer, Pferschy, Pisinger, 2004 , str. 147.
↑ Silvano, 1990 , str. 157.
↑ G. Gallo, P. L. Hammer, B. Simeone. Kvadratické problémy s batohem // Studie matematického programování. - 2009. - 24. února ( vol. 12 ). - S. 132-149 . — ISSN 0303-3929 . Archivováno z originálu 24. října 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. Problémy s batohem: algoritmy a počítačové implementace . - John Wiley & Sons Ltd., 1990. - S. 29,50 . — 296 s. — ISBN 0-471-92420-2 .
↑ Burkov, Gorgidze, Lovetsky, 1974 , s. 225.
↑ 1 2 3 Romanovský I.V. Algoritmy pro řešení extrémních problémů . - Nauka, 1977. - S. 252 -259. — 352 s.
↑ Stephen S. Skiena. Algoritmy. Průvodce rozvojem. - 2. - Petrohrad. : BHV-Petersburg, 2011. - S. 448-451. — 720 s. - ISBN 978-5-9775-0560-4 .
↑ 1 2 Novikov, 2001 , str. 12.
↑ 1 2 Kellerer, Pferschy, Pisinger, 2004 .
↑ Dantzig G. B. Extrémní problémy s diskrétními proměnnými // Oper . Res. - Ústav pro operační výzkum a management věd , 1957. - Sv. 5, Iss. 2. - S. 266-288. - 23 hodin — ISSN 0030-364X ; 1526-5463 – doi:10.1287/OPRE.5.2.266
↑ Ariel Kulik, Hadas Shachnai. Neexistuje žádný EPTAS pro dvourozměrný batoh // Information Processing Letters. — 2010-07-31. - T. 110 , č.p. 16 . — S. 707–710 . - doi : 10.1016/j.ipl.2010.05.031 .
↑ D.I. Batiščev, E.A. Neimark, N.V. Starostin. Aplikace genetických algoritmů k řešení problémů diskrétní optimalizace . - 2007. - Nižnij Novgorod. Archivováno 22. února 2016 na Wayback Machine
↑ 1 2 3 4 5 S. M. Avdošin, A. A. Saveljevová. Kryptoanalýza: současný stav a vyhlídky rozvoje . - S. 38 . Archivováno z originálu 17. března 2016. (Ruština)
↑ G.B. Mathews. O rozdělení čísel (anglicky) . - 1897. - S. 486-490.
↑ Kellerer, Pferschy, Pisinger, 2004 , str. 3.
↑ Kellerer, Pferschy, Pisinger, 2004 , str. 9.
↑ R. Karp. Redukovatelnost mezi kombinatorickými problémy . — 1972.
↑ Riedhammer et al, 2008 , pp. 2436.
↑ Schnaer, 2002 , str. 19.2.
↑ Gabidulin, Kshevetsky, Kolybelnikov, 2011 .
↑ Burkov, Gorgidze, Lovetsky, 1974 , s. 217.
↑ 1 2 3 4 Schnaer, 2002 , str. 19.1.
↑ Kin Ming Lai. Kryptosystémy batohu: Minulost a budoucnost . — 2001. (Ruština)
↑ Salomaa, 1995 , str. 103.

Literatura

v Rusku

Levitin A. V. Algorithms. Úvod do vývoje a analýzy - M .: Williams , 2006. - S. 160-163. — 576 s. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmy: konstrukce a analýza = Úvod do algoritmů. - 2. - M .: "Williams" , 2006. - S. 456-458. — ISBN 0-07-013151-1 .
Robert Sedgwick . Základní algoritmy v C++. Části 1-4. Analýza. Datové struktury. Řazení. Hledání = Algoritmy v C++. Části 1-4. základy. datové struktury. Řazení. Hledání. - 3. - Rusko, Petrohrad: "DiaSoft" , 2002. - S. 688. - ISBN 5-93772-047-4 , 0-201-35088-2.
Burkov V. N. , Gorgidze I. A. , Lovetsky S. E. Aplikované problémy teorie grafů / ed. A. Ya. Gorgidze - Tbilisi : Výpočetní centrum Akademie věd SSSR , 1974. - 231 s.
V. N. Burkov, D. A. Novikov. Prvky teorie grafů . - 2001. - S. 28.
S. Okulov. Programování v algoritmech . - 1. — Binom. Vědomostní laboratoř, 2007. - S. 384. - ISBN 5-94774-010-9 .
B. Schneier. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protokoly, algoritmy a zdrojový kód v C. - 2. - Triumph, 2002. - 816 s. - 3000 výtisků. - ISBN 5-89392-055-4 . Archivováno 18. prosince 2018 na Wayback Machine
A. Salomaa. Šifrování veřejného klíče = Public-Key Cryptography . - M .: Mir, 1995. - S. 102-150. - ISBN 5-03-001991-X. Archivováno 4. března 2016 na Wayback Machine
N. Koblitz. Kurz teorie čísel v kryptografii. - 2. - M . : Vědecké nakladatelství TVP, 2001. - S. 254. - ISBN 5-85484-014-6 .
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Informační bezpečnost : učebnice - M .: MIPT , 2011. - 225 s. — ISBN 978-5-7417-0377-9
Osipyan V. O. O systému informační bezpečnosti založeném na problému batohu // Bulletin Tomské polytechnické univerzity [TPU Bulletin]. - 2006. - T. 309 , č. 2 . - S. 209-212 .

v angličtině

Silvano Martelo, Paolo Tóth. Problémy s batohem . - Velká Británie: Wiley, 1990. - 306 s. — ISBN 0-471-92420-2 .
Kellerer H. , Pferschy U. , Pisinger D. Knapsack Problems (anglicky) - Springer Science + Business Media , 2004. - 548 s. - ISBN 978-3-642-07311-3 - doi:10.1007/978-3-540-24777-7
K. Riedhammer, D. Gillick, B. Favre a D. Hakkani-Tür. Balení batohu na shrnutí schůze . — Brisbane Austrálie: Proc. Interspeech, Brisbane, Austrálie, 2008.
Brettauer K. M. , Shetty B. The nelinear knapsack problem – algorithms and applications (anglicky) // European Journal of Operational Research - Elsevier BV , 2002. - Vol. 138, Iss. 3. - S. 459-472. — ISSN 0377-2217 ; 1872-6860 – doi:10.1016/S0377-2217(01)00179-5

Odkazy

Vítejte v batohu
Problém batohu Eric Grimsom John Guttag - MIT
Řešení problémů batohu v mnoha jazycích
Das Rucksack-Problem (problém s batohem) (německy)

Problém s batohem
Aplikace	Problém batohu v kryptografii Řezací úkol
Kryptosystémy založené na problému batohu	Merkla-Hellman Naccasha - Stern Graham - Shamira
dodatečně	Seznam úkolů o batohu

NP-úplné problémy
Maximalizační problém stohování (balení)	Balení v kontejnerech dvourozměrné balení lineární balení balení podle hmotnosti balení podle hodnoty Problém s batohem
teorie grafů teorie množin	Problém s krytím vertexu Klikněte na problém Problém nezávislé množiny (množiny) Nastavit problém s krytím Steinerův problém Problém cestujícího prodejce Obecný problém cestujícího prodejce
Algoritmické problémy	Problém splnitelnosti pro booleovské vzorce (v konjunktivní normální formě)
Logické hry a hádanky	Generalizované značky (hra v N 2 -1) problém s nejkratším řešením Problémy, jejichž řešení jsou aplikována v Tetrisu Generalizovaný problém sudoku Problém vyplňování latinského čtverce Kakurův úkol
Třídy obtížnosti Operační výzkum Optimalizace Kombinatorická optimalizace Aplikovaná matematika Teorie algoritmů Dynamické programování 21 NP-úplný Karp problém