Seznam úkolů batohu

Problém batohu (nebo batohu) je jedním z kombinatorických optimalizačních problémů . Svůj název získal podle maximalizačního problému sbalit do batohu co nejvíce věcí za předpokladu, že je omezen celkový objem (resp. hmotnost) všech předmětů, které se do batohu vejdou. Proto má úkol několik variant.

Společná pro všechny typy je přítomnost sady položek, se dvěma parametry - hmotností a hodnotou .. Existuje batoh určité kapacity . Úkolem je sestavit batoh s maximální hodnotou předmětů uvnitř při respektování váhového limitu batohu. Obvykle jsou všechny parametry celá čísla, nikoli záporná čísla. $n$ $p_i>0$ $c_i>0$ $, i= 1,2,...,n$ $P$

Batoh 0-1 ( ang. 0-1 Knapsack Problem )

Jedná se o nejběžnější typ batohu. Nechť to nabývá dvou hodnot: pokud je náklad zabalen, a jinak, kde . Úkol: $x_i$ $x_i=1$ $x_i=0$ $i= 1,2,...,n$

maximalizovat $\sum_{i=1}^n c_ix_i$

pokud existuje limit na kapacitu batohu [1] [2] . $\sum_{i=1}^n p_ix_i \le P$

Problém s omezeným batohem _

Každou položku lze vybrat omezený počet opakování. Úkol: $x_i$

maximalizovat $\sum_{i=1}^n c_ix_i$

aby byla splněna kapacitní podmínka $\sum_{i=1}^n p_ix_i \le P$

a pro všechny [3] . $x_i \in(0,1,...,m_i)$ $i= 1,2,...,n$

Číslo se nazývá hranice [3] . $m_i$

Neohraničený problém batohu ( celočíselný batoh )

Každou položku lze vybrat neomezeně mnohokrát. Úkol: $x_i$

maximalizovat $\sum_{i=1}^n c_ix_i$

aby byla splněna kapacitní podmínka $\sum_{i=1}^n p_ix_i \le P$

a celé číslo pro všechny [4] . $x_i\ge0$ $i= 1,2,...,n$

Problém s batohem z [ upravit

Všechny položky jsou rozděleny do tříd . Z každé třídy je povinné vybrat pouze jeden předmět. trvá pouze 0 a 1. Úkol: $x_i$ $s$ $S_{i}$ $x_{i}$

maximalizovat $\sum_{i=1}^n \sum_{j\in S_i} c_{ij}x_{ij}$

aby byla splněna podmínka kapacity, $\sum_{i=1}^n \sum_{j\in S_i} p_{ij}x_{ij} \le P$

$\sum_{j\in S_i}x_{ij}=1$ pro všechny $i= 1,2,...,n$

Problém s více batohy _

Předpokládejme, že máme předměty a batohy ( ). Každá položka, stejně jako dříve, má váhu a hodnotu , každý batoh má svou vlastní kapacitu . . Úkol: $n$ $m$ $m\le n$ $p_j>0$ $c_j>0$ $j= 1,2,...,n$ $P_{i}$ $i= 1,2,...,m$ $x_i\in{0,1}$

maximalizovat ${\displaystyle \sum _{i=1}^{m}\sum _{j=1}^{n}c_{j}x_{ij))$

aby byla podmínka splněna pro všechny , $\sum_{i=1}^n p_{j}x_{ij} \le P_i$ $i= 1,2,...,m$

$\sum _{j=1}^{m}x_{ij}\leq 1$ pro všechny [5] . $i= 1,2,...,n$

vícerozměrného batohu upravit _

Pokud je na batohu více než jedno omezení, jako je objem a hmotnost, problém se nazývá m-rozměrný problém batohu. Například pro neomezenou možnost:

maximalizovat $\sum_{i=1}^n c_ix_i$

takže , $\sum_{i=1}^n p_{ij}x_i \le P_j$ $j= 1,2,...,m$

a pro všechny [4] . $x_i\ge0$ $i= 1,2,...,n$

Problém kvadratického batohu _

Kvadratický problém s batohem je modifikací klasických problémů s batohem s hodnotou, která je kvadratickou formou . Nechť je vektor, který určuje, kolik kopií každé položky bude v batohu. Úkol: $x=(x_{1},..,x_{n})$

maximalizovat $x^{T}Qx$

za podmínek , , nebo $\sum_{i=1}^n p_ix_i \le P$ ${\displaystyle x\in B^{n))$

minimalizovat $x^{T}Qx$

za podmínek ,. $\sum _{i=1}^{n}p_{i}x_{i}\geq P$ ${\displaystyle x\in B^{n))$

Zároveň nezáporná jednoznačná matice velikosti stanovuje omezení počtu položek [6] . $Q$ $n\krát n$ $B^{n}$

Poznámky

↑ Burkov, 1974 , s. 217.
↑ Silvano, 1990 , str. 2.
↑ 1 2 Pisinger, 1995 , s. 127.
↑ 1 2 Pisinger, 1995 , s. 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.

Literatura

v Rusku

V. N. Burkov, I. A. Gorgidze, S. E. Lovetsky. Aplikované problémy teorie grafů. - M. , 1974. - 232 s.

v angličtině

Silvano Martelo, Paolo Tóth. Problémy s batohem. - Wiley, 1990. - 306 s.
David Pisinger. Problémy s batohem . - 1995. Archivováno 22. prosince 2012 na Wayback Machine

Odkazy

Algoritmus batohu

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