+ - problema de mochila

9

Dado un conjunto de artículos, cada uno con un peso y un valor, determine el número de cada artículo para incluir en una colección de modo que el peso total sea menor o igual a un límite dado y el valor total sea lo más grande posible.

Wikipedia para más información

Por ejemplo, se le puede asignar un peso máximo de 15 y objetos con valores / masas como [5,2], [7,4] [1,1]y generaría [7,0,1]7 [5 <value>, 2 <mass>]objetos y 1 [1 <value>, 1 <mass>]objeto para una puntuación de 36.

Reglas

La entrada se puede tomar en cualquier formato razonable

La salida también es un formato flexible,

No puede usar bibliotecas que no sean estándar. Si usted tiene que instalar o descargar cualquier biblioteca de usar separado de la configuración inicial, entonces es que no permitió

Los objetos pueden tener masa y valor negativos (es decir, -1, -1)

Se requieren respuestas óptimas

Victorioso

El código más corto gana

Masa negativa y valor?

Esta es una parte clave de este desafío. Digamos que tiene un objeto con elementos (masa, valor) como [4,3],[-1,-1]y una bolsa con capacidad de 15. Podría poner 3 de los primeros y anotar 9 o poner 4 de los primeros y uno de los -1, -1 objetar un puntaje de 11.

code-golf optimization Christopher
fuente
sandbox
Christopher
¿Podemos suponer que ningún objeto tendrá masa no positiva?
HyperNeutrino
@HyperNeutrino un segundo eliminando para ediciones
Christopher
2
¿Podemos suponer que todo es un número entero? Además, ¿tendremos que tratar casos como [[2, 1], [-1, -1]] donde el valor total puede hacerse arbitrariamente grande?
55
El título es engañoso. Debido a los pesos negativos, este no es el problema de la mochila, sino una variación del problema de programación lineal.
ngn

Respuestas:

2

Pyth, 18 bytes

h.MshMZfghQseMTy*F

Salidas como una lista de pares [valor, peso]. Horriblemente ineficiente, pero es NP completo.
Pruébalo aquí

Explicación

h.MshMZfghQseMTy*F
               y*FQ  Get all sets with up to <capacity> of each item.
       fghQseMT      Choose the sets whose total weight fits in the bag.
 .MshMZ              Choose those with the highest value.
h                    Take the first.

fuente