algoritmo para encontrar la mejor combinación

Question

Supongamos que tengo una lista de 100 productos, cada uno de los cuales tiene un precio. Cada uno también tiene una medida de energía (kJ).

¿Sería posible encontrar la mejor combinación de 15 productos por menos de $ 10 de los cuales la suma de la energía (kJ) era máxima, usando la programación?

Sé C#, pero cualquier idioma está bien. Aclamaciones.

Actualización: Tener un trozo de trozo de encontrar algún código fuente de muestra para el problema de la mochila. ¿Alguien tiene alguna o sabe dónde encontrarla? Estuve buscando en Google por unas horas y tengo que ordenarlo mañana si es posible. Ejército de reserva.

Answer 1

http://en.wikipedia.org/wiki/Knapsack_problem

El problema mochila o problema mochila es un problema en combinatorial optimization: Dado un conjunto de elementos, cada uno con un peso y un valor, determinar el número de cada elemento a incluir en una colección para que el peso total sea menor o igual a un límite dado y el valor total sea lo más grande posible. Su nombre se deriva del problema enfrentado por alguien que está limitado por un tamaño fijo knapsack y debe llenarlo con los artículos más valiosos ...

Answer 2

Eso se parece mucho a la problema de la mochila. Hay varios enfoques (orden que desciende por densidad de energía, por ejemplo).

Answer 3

Esto me recuerda el famoso algoritmo de mochila

http://en.wikipedia.org/wiki/Knapsack_problem

Answer 4

Esto suena más como un problema linear programming.

De manera informal, la programación lineal determina la manera de lograr el mejor resultado (como máximo beneficio o costo más bajo) en un modelo matemático dado y dado alguna lista de requisitos representados como ecuaciones lineales.

Compruebe hacia fuera Simplex Method.

Answer 5

Esto en Integer Linear Programming, optimizando una ecuación lineal sujeta a restricciones lineales, donde todas las variables y coeficientes son enteros.

¿Quieres variables de includeItem1, ..., includeItemN con limitaciones 0 ≤ i includeItem ≤ 1 para todos los valores de i y includeItem1 + ... + includeItemN ≤ 15, y includeItem1 * priceItem1 + .. . ≤ 10, maximizando includeItem1 * kilojouleItem1 + ....

Stick que en su número entero favorita solucionador de programación lineal y obtener la solución :)

Véase también http://en.wikipedia.org/wiki/Linear_programming

No tiene sentido decir que su problema particular es NP-completo, pero es una ejemplo de un problema NP-completo (tipo de), por lo que podría no haber un teóricamente manera rápida de hacerlo. Dependiendo de qué tan cerca de la optimalidad desea obtener y qué tan rápido funcionan los solucionadores de ILP, podría ser factible en la práctica.

No creo que su problema sea un caso especial de ILP que lo hace particularmente fácil de resolver. Al verlo como un problema parecido a una mochila, podría restringirse a mirar todos los subconjuntos de 1..100 que tienen como máximo (o exactamente) 15 elementos, que es un polinomio en n --- es n-elija-15, que es menor que (n^15)/(15!), pero eso no es terriblemente útil cuando n = 100.

Si desea recomendaciones para los programas de resolución, he intentado con glpk y me pareció agradable de usar. En caso de que quiera algo que le cueste dinero, mi conferencista siempre habló sobre CPLEX como ejemplo.

Answer 6

Este es el problema de la mochila si puede elegir un producto o no. Si puede elegir valores fraccionarios de productos, entonces puede resolver esto con el método símplex, pero el problema de mochila fraccional tiene una solución simple.

Ordene los artículos por relación energía/precio, escoja el 100% de los más altos hasta que se quede sin dinero, luego elija un valor fraccionario del más alto restante.

Por ejemplo, si los precios son 4,3,5,4 y 3,5,2,7 energías son el ordenamiento es

7/4, 5/3, 3/4, 2/5

por lo que sería recoger artículos 4 y 2, que costaría 7 $, con los $ 3 restantes que iba a comprar el 75% de la primera partida de un precio de $ 3 y una energía de 3 * .75 = 2,25

Este daría una energía total de 14.25

Tenga en cuenta que permitir valores fraccionarios le dará un valor objetivo más alto que solo permitir 0% o 100%, por lo que ninguna solución entera será mejor que 14.25 (o 14 para el caso, ya que el valor objetivo tiene que ser un número entero).

Para resolver el problema original de la mochila, puede usar una ramificación y encuadernación que debería funcionar bien en la práctica. Suponga que tiene una solución candidata actual con un valor objetivo de z *

1. Resuelva el problema relajado, donde permite los pesos fraccionarios. Si el valor es menor que z *, descarte esta rama.
2. Calcule un nuevo valor z que es la solución encontrada sin la última fracción de peso, si este valor es mayor que z *, reemplace z * con su nuevo valor
3. Elija un ítem (digamos el primero en la lista, más rentable) y forman dos subproblemas, uno donde debe incluirlo en la solución y otro donde no puede incluirlo en la solución (este es el paso de bifurcación).
4. Mientras tenga subproblemas pendientes de resolver, elija uno y vuelva al paso 1.

Tenga en cuenta que cuando crea el subproblema donde debe elegir un artículo, simplemente resta su precio del presupuesto y agrega el valor al beneficio, ahora tiene un problema menor que resolver.

Para una descripción más detallada mire Branch and Bound en Wikipedia.

Answer 7

El Stony Brook Algoritmo repositorio enumera implementations for the knapsack problem.

Su libro The Algorithm Design Manual tiene este tipo de información para una amplia gama de problemas.

Answer 8

Debería ser posible solucionar el problema con Cream for Java. También hay una versión disponible para C# CSharpCream.

Answer 9

Sí, como todos señalaron, este es un problema complejo de mochila. Sin embargo, algo tan simple podría ser lo suficientemente bueno ...

SELECT TOP 15 * 
FROM Product 
WHERE Price < 10 
ORDER BY Energy DESC