Un algoritmo de embalaje & # 8230; mas o menos

Question

Dada una matriz de elementos, cada uno de los cuales tiene un valor y cost , cuál es el mejor algoritmo determina los elementos necesarios para alcanzar un valor mínimo en el costo mínimo? por ejemplo:

Item: Value -> Cost
-------------------
A     20   -> 11
B     7    -> 5
C     1    -> 2

MinValue = 30
naive solution: A + B + C + C + C. Value: 30, Cost 22
best option: A + B + B.            Value: 34, Cost 21

Tenga en cuenta que el valor global: la relación de costos al final es irrelevante ( A + A le daría la mejor relación calidad-precio, pero A + B + B es una opción más barata que alcanza el valor mínimo).

Answer 1

Este es el problema de la mochila. (Es decir, la versión de decisión de este problema es la misma que la versión de decisión del problema de la mochila, aunque la versión de optimización del problema de la mochila generalmente se establece de manera diferente). Es NP-hard (lo que significa que no se conoce ningún algoritmo que sea polinomio en el "tamaño" - número de bits - en la entrada). Pero si sus números son pequeños (el mayor '' valor '' en la entrada, digamos; los costos no importan), entonces hay una solución de programación dinámica simple.

Deje que el mejor [v] sea el costo mínimo para obtener un valor de (exactamente) v. Luego, puede calcular los mejores valores [] para todos los v, (inicializando todos los mejores [v] hasta el infinito y):

best[0] = 0
best[v] = min_(items i){cost[i] + best[v-value[i]]}

Luego busque en el mejor [v] valores hasta el mínimo que desee más el valor más grande; el más pequeño de ellos le dará el costo.

Si desea los elementos reales (y no solo el costo mínimo), puede mantener algunos datos adicionales o simplemente mirar a través del conjunto de los mejores [] sy deducir de ellos.

Answer 2

Este problema se conoce como programación lineal entera. Es NP-duro. Sin embargo, para pequeños problemas como su ejemplo, es trivial hacer unas pocas líneas de código rápidas para simplemente aplicar la fuerza bruta a todas las combinaciones bajas de opciones de compra.

NP-hard no significa imposible o incluso costoso, significa que su problema se vuelve más lento de resolver con problemas de mayor escala. En su caso con solo tres elementos, puede resolver esto en solo microsegundos.

Para la pregunta exacta de cuál es el mejor algoritmo en general ... hay libros de texto completos en él. Un buen comienzo es buena y antigua Wikipedia.

Answer 3

Editar Esta respuesta está redactada por ser objetivamente incorrecta. Seguir los consejos en esto solo le causará daño.

Este no es realmente el problema de la mochila, porque supone que no puede empacar más artículos de los que hay espacio en algún contenedor. En su caso, desea encontrar la combinación más barata que llene el espacio, teniendo en cuenta el hecho de que puede producirse un desbordamiento.

Mi solución, que no sé es la óptima, pero debería estar bastante cerca, sería calcular para cada artículo la relación costo beneficio, encontrar el artículo con el beneficio de costo más alto y llenar la estructura con este artículo hasta No hay espacio para un artículo más. Luego, probaría para ver si había una combinación con cualquiera de los otros elementos disponibles que podría llenar el espacio disponible por menos del costo de uno de los artículos más baratos y luego, si existe una solución, use esa combinación o use uno más de los artículos más baratos.

Enmendar Esto en realidad también puede ser NP-completo, pero aún no estoy seguro. De todos modos, para todos los fines prácticos, esta variación debería ser mucho más rápida que la solución ingenua.