Lista de tareas de la mochila

El problema de la mochila (o morral) es uno de los problemas de optimización combinatoria . Obtuvo su nombre del problema de maximización de empacar tantas cosas como sea posible en una mochila, siempre que el volumen total (o peso) de todos los artículos que pueden caber en una mochila sea limitado. Por lo tanto, la tarea tiene varias variedades.

Común a todos los tipos es la presencia de un conjunto de artículos, con dos parámetros: peso y valor Hay una mochila de cierta capacidad . La tarea es armar una mochila con el valor máximo de los artículos dentro, respetando el límite de peso de la mochila. Por lo general, todos los parámetros son números enteros, no números negativos. $norte$ $p_i>0$ $c_i>0$ $, i= 1,2,...,n$ $PAGS$

Mochila 0-1 ( ing. 0-1 Problema de mochila )

Este es el tipo de mochila más común. Que tome dos valores: si la carga está embalada, y en caso contrario, donde . Una tarea: $x_i$ $x_i=1$ $x_i=0$ $i= 1,2,...,n$

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

si hay un límite en la capacidad de la mochila [1] [2] . $\sum_{i=1}^n p_ix_i \le P$

Problema de la mochila acotada _

Cada elemento se puede seleccionar un número limitado de veces. Una tarea: $x_i$

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

para que se cumpla la condición de capacidad $\sum_{i=1}^n p_ix_i \le P$

y para todos [3] . $x_i \in(0,1,...,m_i)$ $i= 1,2,...,n$

El número se llama límite [3] . $mi$

Problema de la mochila sin límites ( mochila entera )

Cada elemento se puede seleccionar un número ilimitado de veces. Una tarea: $x_i$

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

para que se cumpla la condición de capacidad $\sum_{i=1}^n p_ix_i \le P$

y un entero para todos [4] . $x_i\ge0$ $i= 1,2,...,n$

Problema de mochila de [ editar

Todos los elementos se dividen en clases . Es obligatorio seleccionar solo una materia de cada clase. toma solo 0 y 1. Tarea: $x_i$ $s$ $Si}$ $x_{yo}$

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

para que se cumpla la condición de capacidad, $\sum_{i=1}^n \sum_{j\in S_i} p_{ij}x_{ij} \le P$

$\sum_{j\en S_i}x_{ij}=1$ para todos $i= 1,2,...,n$

Problema de mochila múltiple _

Supongamos que tenemos artículos y mochilas ( ). Cada artículo, como antes, tiene un peso y un valor , cada mochila, respectivamente, tiene su propia capacidad en . . Una tarea: $norte$ $metro$ $m \ le n$ $p_j>0$ $c_j>0$ $j= 1,2,...,n$ $Pi}$ $i= 1,2,...,m$ $x_i\in{0,1}$

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

para que la condición se cumpla para todos , $\sum_{i=1}^n p_{j}x_{ij} \le P_i$ $i= 1,2,...,m$

$\sum_{j=1}^{m}x_{ij}\leq 1$ para todos [5] . $i= 1,2,...,n$

multidimensional de la mochila editar _

Si hay más de una restricción en la mochila, como el volumen y el peso, el problema se denomina problema de mochila m-dimensional. Por ejemplo, para la opción sin restricciones:

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

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

y para todos [4] . $x_i\ge0$ $i= 1,2,...,n$

Problema cuadrático de la mochila _

El problema cuadrático de la mochila es una modificación de los problemas clásicos de la mochila con un valor que es una forma cuadrática de . Sea un vector que especifique cuántas copias de cada artículo habrá en la mochila. Una tarea: ${\ estilo de visualización x = (x_{1},..,x_{n})}$

maximizar ${\ estilo de visualización x^{T} Qx}$

bajo las condiciones , o $\sum_{i=1}^n p_ix_i \le P$ ${\ estilo de visualización x \ en B ^ {n}}$

minimizar ${\ estilo de visualización x^{T} Qx}$

en condiciones , . $\sum _{i=1}^{n}p_{i}x_{i}\geq P$ ${\ estilo de visualización x \ en B ^ {n}}$

Al mismo tiempo , una matriz definida no negativa de tamaño establece restricciones en el número de elementos [6] . $q$ $n\veces n$ ${\ estilo de visualización B ^ {n}}$

Notas

↑ Burkov, 1974 , pág. 217.
↑ Silvano, 1990 , pág. 2.
↑ 1 2 Pisinger, 1995 , pág. 127.
↑ 1 2 Pisinger, 1995 , pág. 147.
↑ Silvano, 1990 , pág. 157.
↑ G. Gallo, P. L. Hammer, B. Simeone. Problemas de mochila cuadráticos // Estudios de programación matemática. - 2009. - 24 de febrero ( vol. 12 ). - pág. 132-149 . — ISSN 0303-3929 . Archivado desde el original el 24 de octubre de 2016.

Literatura

en ruso

V. N. Burkov, I. A. Gorgidze, S. E. Lovetsky. Problemas aplicados de teoría de grafos. - M. , 1974. - 232 p.

en inglés

Silvano Martelo, Paolo Toth. Problemas con la mochila. - Wiley, 1990. - 306 p.
David Pisanger. Problemas con la mochila . - 1995. Archivado el 22 de diciembre de 2012 en Wayback Machine .

Enlaces

Algoritmo de mochila

El problema de la mochila
Aplicaciones	Problema de la mochila en criptografía Tarea de corte
Criptosistemas basados en el problema de la mochila	Merkla-Hellman Naccasha - popa Graham - Shamira
Además	Lista de tareas sobre la mochila