Lista sarcinilor rucsac

Problema rucsacului (sau rucsacului) este una dintre problemele de optimizare combinatorie . Și-a luat numele de la problema maximizării de a împacheta cât mai multe lucruri într-un rucsac, cu condiția ca volumul total (sau greutatea) tuturor articolelor care pot încăpea într-un rucsac să fie limitat. Prin urmare, sarcina are mai multe varietăți.

Comun tuturor tipurilor este prezența unui set de articole, cu doi parametri - greutate și valoare . Există un rucsac de o anumită capacitate . Sarcina este de a asambla un rucsac cu valoarea maximă a articolelor din interior, respectând în același timp limita de greutate a rucsacului. De obicei, toți parametrii sunt numere întregi, nu numere negative. $n$ $p_i>0$ $c_i>0$ $, i= 1,2,...,n$ $P$

Rucsac 0-1 ( ing. 0-1 Problemă la rucsac )

Acesta este cel mai comun tip de rucsac. Lăsați să ia două valori: dacă încărcătura este ambalată și , în caz contrar, unde . O sarcină: $x_i$ $x_i=1$ $x_i=0$ $i= 1,2,...,n$

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

dacă există o limită a capacității rucsacului [1] [2] . $\sum_{i=1}^n p_ix_i \le P$

Problemă de rucsac limitat _

Fiecare articol poate fi selectat de un număr limitat de ori. O sarcină: $x_i$

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

astfel încât să fie îndeplinită condiția de capacitate $\sum_{i=1}^n p_ix_i \le P$

și pentru toți [3] . $x_i \in(0,1,...,m_i)$ $i= 1,2,...,n$

Numărul se numește graniță [3] . $m_i$

Problemă nelimitată de rucsac ( rucsac întreg )

Fiecare articol poate fi selectat de un număr nelimitat de ori. O sarcină: $x_i$

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

astfel încât să fie îndeplinită condiția de capacitate $\sum_{i=1}^n p_ix_i \le P$

și un număr întreg pentru toate [4] . $x_i\ge0$ $i= 1,2,...,n$

Problemă la rucsac cu [ editează

Toate articolele sunt împărțite în clase . Este obligatoriu să selectați un singur subiect din fiecare clasă. ia doar 0 și 1. Sarcină: $x_i$ $s$ $Si}$ $x_{i}$

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

astfel încât condiția de capacitate să fie îndeplinită, $\sum_{i=1}^n \sum_{j\in S_i} p_{ij}x_{ij} \le P$

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

Problemă cu rucsacuri multiple _

Să presupunem că avem articole și rucsacuri ( ). Fiecare articol, ca și până acum, are o greutate și o valoare , fiecare rucsac, respectiv, are propria capacitate la . . O sarcină: $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}$

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

astfel încât condiția să fie îndeplinită pentru toți , $\sum_{i=1}^n p_{j}x_{ij} \le P_i$ $i= 1,2,...,m$

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

rucsac multidimensional editează _

Dacă există mai mult de o constrângere asupra rucsacului, cum ar fi volumul și greutatea, problema se numește o problemă de rucsac m-dimensională. De exemplu, pentru opțiunea nerestricționată:

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

astfel încât , $\sum_{i=1}^n p_{ij}x_i \le P_j$ $j= 1,2,...,m$

și pentru toți [4] . $x_i\ge0$ $i= 1,2,...,n$

Problemă la rucsac cuadratic _

Problema rucsacului pătratic este o modificare a problemelor clasice de rucsac cu o valoare care este o formă pătratică a . Să fie un vector care specifică câte copii ale fiecărui articol vor fi în rucsac. O sarcină: $x=(x_{1},...,x_{n})$

maximiza $x^{T}Qx$

în condițiile , , sau $\sum_{i=1}^n p_ix_i \le P$ $x\in B^{n)$

minimiza $x^{T}Qx$

in conditii , . $\sum _{i=1}^{n}p_{i}x_{i}\geq P$ $x\in B^{n)$

În același timp , o matrice definită nenegativă de mărime stabilește restricții asupra numărului de articole [6] . $Q$ $n\ ori n$ $B^{n)$

Note

↑ 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. Probleme de rucsac cuadratic // Studii de programare matematică. - 2009. - 24 februarie ( vol. 12 ). - P. 132-149 . — ISSN 0303-3929 . Arhivat din original pe 24 octombrie 2016.

Literatură

in rusa

V. N. Burkov, I. A. Gorgidze, S. E. Lovetsky. Probleme aplicate ale teoriei grafurilor. - M. , 1974. - 232 p.

în limba engleză

Silvano Martelo, Paolo Toth. Probleme la rucsac. - Wiley, 1990. - 306 p.
David Pisinger. Probleme la rucsac . - 1995. Arhivat 22 decembrie 2012 la Wayback Machine

Link -uri

Algoritm de rucsac

Problema rucsacului
Aplicații	Problemă la rucsac în criptografie Sarcina de tăiere
Criptosisteme bazate pe problema rucsacului	Merkla-Hellman Naccasha - Pupa Graham - Shamira
În plus	Lista sarcinilor despre rucsac