Ryggsäcksuppgiftslista

Problemet med ryggsäck (eller ryggsäck) är ett av de kombinatoriska optimeringsproblemen . Den har fått sitt namn från maximeringsproblemet att packa in så många saker som möjligt i en ryggsäck, förutsatt att den totala volymen (eller vikten) av alla föremål som får plats i en ryggsäck är begränsad. Därför har uppgiften flera varianter.

Gemensamt för alla typer är närvaron av en uppsättning artiklar, med två parametrar - vikt och värde . Det finns en ryggsäck med en viss kapacitet . Uppgiften är att montera en ryggsäck med maxvärdet av föremålen inuti, samtidigt som ryggsäckens viktgräns respekteras. Vanligtvis är alla parametrar heltal, inte negativa tal. $n$ $p_i>0$ $c_i>0$ $, i= 1,2,...,n$ $P$

Ryggsäck 0-1 ( eng. 0-1 Knapsack Problem )

Detta är den vanligaste typen av ryggsäck. Låt det ta två värden: om lasten är packad, och annars, var . En uppgift: $x_i$ $x_i=1$ $x_i=0$ $i= 1,2,...,n$

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

om det finns en begränsning på ryggsäckens kapacitet [1] [2] . $\sum_{i=1}^n p_ix_i \le P$

Bounded Knapsack Problem _

Varje objekt kan väljas ett begränsat antal gånger. En uppgift: $x_i$

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

så att kapacitetsvillkoret är uppfyllt $\sum_{i=1}^n p_ix_i \le P$

och för alla [3] . $x_i \in(0,1,...,m_i)$ $i= 1,2,...,n$

Numret kallas gränsen [3] . $mi$

Obegränsat ryggsäcksproblem ( heltalsryggsäck )

Varje objekt kan väljas ett obegränsat antal gånger. En uppgift: $x_i$

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

så att kapacitetsvillkoret är uppfyllt $\sum_{i=1}^n p_ix_i \le P$

och ett heltal för alla [4] . $x_i\ge0$ $i= 1,2,...,n$

knepsäck [ redigera _

Alla föremål är indelade i klasser . Det är obligatoriskt att endast välja ett ämne från varje klass. tar bara 0 och 1. Uppgift: $x_i$ $s$ $Si}$ $x_{i}$

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

så att kapacitetsvillkoret är uppfyllt, $\sum_{i=1}^n \sum_{j\in S_i} p_{ij}x_{ij} \le P$

$\sum_{j\in S_i}x_{ij}=1$ för alla $i= 1,2,...,n$

Problem med flera ryggsäckar _

Anta att vi har föremål och ryggsäckar ( ). Varje vara har som tidigare en vikt och ett värde , varje ryggsäck har sin egen kapacitet på . . En uppgift: $n$ $m$ $m\le n$ $p_j>0$ $c_j>0$ $j= 1,2,...,n$ $Pi}$ $i= 1,2,...,m$ $x_i\in{0,1}$

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

så att villkoret är uppfyllt för alla , $\sum_{i=1}^n p_{j}x_{ij} \le P_i$ $i= 1,2,...,m$

$\sum _{j=1}^{m}x_{ij}\leq 1$ för alla [5] . $i= 1,2,...,n$

Flerdimensionellt ryggsäcksproblem redigera _

Om det finns mer än en begränsning på ryggsäcken, såsom volym och vikt, kallas problemet ett m-dimensionellt ryggsäcksproblem. Till exempel, för det obegränsade alternativet:

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

så att , $\sum_{i=1}^n p_{ij}x_i \le P_j$ $j= 1,2,...,m$

och för alla [4] . $x_i\ge0$ $i= 1,2,...,n$

Kvadratiskt ryggsäcksproblem _ _

Det kvadratiska ryggsäcksproblemet är en modifiering av de klassiska ryggsäcksproblemen med ett värde som är en kvadratisk form av . Låt vara en vektor som anger hur många kopior av varje föremål som kommer att finnas i ryggsäcken. En uppgift: $x=(x_{1},..,x_{n})$

maximera $x^{T}Qx$

under villkoren , eller $\sum_{i=1}^n p_ix_i \le P$ ${\displaystyle x\in B^{n))$

minimera $x^{T}Qx$

under förhållanden , . $\sum _{i=1}^{n}p_{i}x_{i}\geq P$ ${\displaystyle x\in B^{n))$

Samtidigt sätter en icke-negativ bestämd matris av storlek begränsningar för antalet objekt [6] . $F$ $n\ gånger n$ ${\displaystyle B^{n))$

Anteckningar

↑ Burkov, 1974 , sid. 217.
↑ Silvano, 1990 , sid. 2.
↑ 1 2 Pisinger, 1995 , sid. 127.
↑ 1 2 Pisinger, 1995 , sid. 147.
↑ Silvano, 1990 , sid. 157.
↑ G. Gallo, P. L. Hammer, B. Simeone. Kvadratiska ryggsäcksproblem // Mathematical Programming Studies. - 2009. - 24 februari ( vol. 12 ). - S. 132-149 . — ISSN 0303-3929 . Arkiverad från originalet den 24 oktober 2016.

Litteratur

på ryska

V. N. Burkov, I. A. Gorgidze, S. E. Lovetsky. Tillämpade problem inom grafteori. - M. , 1974. - 232 sid.

på engelska

Silvano Martelo, Paolo Toth. Ryggsäcksproblem. - Wiley, 1990. - 306 sid.
David Pisinger. Knapsäcksproblem . - 1995. Arkiverad 22 december 2012 på Wayback Machine

Länkar

Ryggsäcksalgoritm

ryggsäcksproblemet
Ansökningar	Knapsäcksproblem i kryptografi Skärningsuppgift
Kryptosystem baserade på ryggsäcksproblemet	Merkla-Hellman Naccasha - Stern Graham - Shamira
Dessutom	Lista över uppgifter om ryggsäck