Hátizsák feladatlista

A hátizsák (vagy hátizsák) probléma a kombinatorikus optimalizálási problémák egyike . Nevét arról a maximalizálási problémáról kapta, hogy minél több dolgot csomagoljunk egy hátizsákba, feltéve, hogy a hátizsákba elférő összes tárgy teljes térfogata (vagy súlya) korlátozott. Ezért a feladatnak több fajtája van.

Minden típusra jellemző, hogy van egy elemkészlet , két paraméterrel - súly és érték . Van egy bizonyos kapacitású hátizsák . A feladat egy olyan hátizsák összeállítása, amelyben a benne lévő tárgyak maximális értéke van, a hátizsák súlyhatárának betartása mellett. Általában minden paraméter egész szám, nem negatív szám. $n$ $p_i>0$ $c_i>0$ $, i= 1,2,...,n$ $P$

Hátizsák 0-1 ( eng. 0-1 Hátizsák Probléma )

Ez a hátizsák leggyakoribb típusa. Legyen két érték: ha a rakomány be van csomagolva, és egyébként hol . Egy feladat: $x_i$ $x_i=1$ $x_i=0$ $i= 1,2,...,n$

maximalizálni $\sum_{i=1}^n c_ix_i$

ha a hátizsák befogadóképessége korlátozott [1] [2] . $\sum_{i=1}^n p_ix_i \le P$

Határozott hátizsák probléma _

Minden elem korlátozott számú alkalommal választható ki. Egy feladat: $x_i$

maximalizálni $\sum_{i=1}^n c_ix_i$

hogy a kapacitásfeltétel teljesüljön $\sum_{i=1}^n p_ix_i \le P$

és mindenkinek [3] . $x_i \in(0,1,...,m_i)$ $i= 1,2,...,n$

A számot határnak [3] nevezzük . $m_i$

Korlátlan hátizsák probléma ( integer hátizsák )

Minden elem korlátlan számú alkalommal választható ki. Egy feladat: $x_i$

maximalizálni $\sum_{i=1}^n c_ix_i$

hogy a kapacitásfeltétel teljesüljön $\sum_{i=1}^n p_ix_i \le P$

és egy egész szám mindenre [4] . $x_i\ge0$ $i= 1,2,...,n$

hátizsák probléma [ szerkesztés

Minden elem osztályokra van osztva . Minden osztályból csak egy tantárgyat kötelező kiválasztani. csak 0 és 1. Feladat: $x_i$ $s$ $S_{i}$ $x_{i}$

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

hogy a kapacitás feltétel teljesüljön, $\sum_{i=1}^n \sum_{j\in S_i} p_{ij}x_{ij} \le P$

$\sum_{j\in S_i}x_{ij}=1$ mindenkinek $i= 1,2,...,n$

Több hátizsák probléma _

Tegyük fel, hogy vannak tárgyaink és hátizsákjaink ( ). Minden elemnek, mint korábban, van súlya és értéke , minden hátizsáknak saját kapacitása van . . Egy feladat: $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}$

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

hogy a feltétel mindenki számára teljesüljön , $\sum_{i=1}^n p_{j}x_{ij} \le P_i$ $i= 1,2,...,m$

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

Többdimenziós hátizsák szerkesztés _

Ha egynél több kényszer van a hátizsákon, például térfogat és súly, a problémát m-dimenziós hátizsák-problémának nevezzük. Például a korlátlan opcióhoz:

maximalizálni $\sum_{i=1}^n c_ix_i$

szóval , $\sum_{i=1}^n p_{ij}x_i \le P_j$ $j = 1,2,...,m$

és mindenkinek [4] . $x_i\ge0$ $i= 1,2,...,n$

Kvadratikus hátizsák probléma _

A kvadratikus hátizsák-probléma a klasszikus hátizsák-problémák olyan módosítása, amelynek értéke a négyzetes formája . Legyen egy vektor, amely megadja, hogy az egyes elemek hány példányban kerüljenek a hátizsákba. Egy feladat: $x=(x_{1},..,x_{n})$

maximalizálni $x^{T}Qx$

feltételek mellett , , vagy $\sum_{i=1}^n p_ix_i \le P$ ${\displaystyle x\in B^{n))$

minimalizálni $x^{T}Qx$

feltételek mellett , . $\sum _{i=1}^{n}p_{i}x_{i}\geq P$ ${\displaystyle x\in B^{n))$

Ugyanakkor a méret nemnegatív definit mátrixa korlátozza az elemek számát [6] . $K$ $n\szer n$ ${\megjelenítési stílus B^{n))$

Jegyzetek

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

Irodalom

oroszul

V. N. Burkov, I. A. Gorgidze, S. E. Lovetsky. A gráfelmélet alkalmazott problémái. - M. , 1974. - 232 p.

angolul

Silvano Martelo, Paolo Toth. Hátizsák problémák. - Wiley, 1990. - 306 p.
David Pisinger. Hátizsák problémák . - 1995. Archiválva : 2012. december 22. a Wayback Machine -nál

Linkek

Hátizsák algoritmus

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