¿Cuál es el nombre del algoritmo que "invierte" el problema de la mochila?

Question

Sé de la mochila problema. Quiero encontrar un algoritmo que "invierte" el problema de la mochila. Mi problema es el siguiente:

Dado un conjunto de elementos, cada uno con un peso y un valor, determinar el número de cada elemento para incluir en una colección, de modo que el peso total es mayor que o igual a un determinado límite y el valor total es tan pequeño como sea posible.

$$\min \sum _{i=1}^{n}v_{i}x_{i}$$ sujeto a

$$\sum _{i=1}^{n}w_{i}x_{i}\geq W $$

Es NP-duro problema?

Answer 1

Creo que la respuesta es sí, si el número de cada elemento está acotada. Supongamos que se tienen dos bolsas, es decir, $B_1$ $B_2$ y desea distribuir los elementos en estos dos bolsas. Se desea determinar el número de cada elemento a incluir en $B_1$ tal que $$ \sum_{i=1}^n v_ix_i $$ es minimizado y, al mismo tiempo, $$ \sum_{i=1}^n w_ix_i \geq W $$ Esto es equivalente a determinar el número de cada elemento a incluir en $B_2$ tal que $$ \sum_{i=1}^n v_ix_i $$ es maximizada y, al mismo tiempo, $$ \sum_{i=1}^n w_ix_i \leq W' $$ donde $W' = \text{total weights of the items } - W$.