¿Qué algoritmo debo usar para encontrar la solución más cercana a un total dado usando una lista de enteros?

Question

Mi problema es esto:

Digamos que tengo una lista arbitraria de enteros a [2013, 54, 3, 32 1, 23 ...]

¿Cuál es la mejor estrategia para encontrar cuál de esos números debería agregar juntos para tener una suma igual o más cercana a un número dado?

Obviamente, siempre existe el método de fuerza bruta, pero estoy interesado en saber si hay una más optimizada.

Answer 1

Al empacar el equipaje en un automóvil, pone los artículos más importantes en primer lugar y luego se ajustan a los artículos más pequeños que los rodean. Por analogía, un enfoque heurístico de su problema es comenzar con el miembro de su conjunto que sea lo más grande posible mientras aún es menor que su objetivo. Luego repita el proceso por la diferencia entre su total actual y su objetivo, y así sucesivamente. Esto se conoce como una algoritmo codicioso .

Por ejemplo, si su set es $ \ {2,3,5,8,13,21, 34 \} $ y su objetivo es $ 32 $ , comience con $ 21 $ (el mayor valor menos que $ 32 $ ), luego agregue $ 8 $ (porque este es el valor grande menor que $ 32-21= 11 $ < / SPAN>), y luego agregue $ 3 $ .

Un algoritmo codicioso es rápido y simple, pero no siempre le dará la mejor solución. Por ejemplo, si su set es $ \ {1, 5, 23, 26 \} $ y su objetivo es $ 30 $ Luego, el algoritmo codicioso le da $ 26 + 1= 27 $ , mientras que la mejor solución es $ 23 + 5 + 1= 29 $ .

Answer 2

El problema es NP-Completo, pero polinomio en el valor del número dado, con un grado polinomial bastante bajo. Solo es difícil si los números involucrados son grandes.

Clasificación de más pequeños a más grande y agregando hasta que no se ajusten a ningún número, no es muy inteligente, ya que es probable que sea un número bastante grande que no se ajuste, y no se acercará a la suma deseada. Mucho mejor para clasificar de más grande a más pequeño y agregar los números más grandes primero.

Ahora, si tiene artículos con una suma Cerrar a S, puede intentar mejorar esto. Por ejemplo, si su suma es demasiado pequeña para 117, pero el artículo no utilizado más pequeño es 317, lo intentaría si tiene un artículo X en su lista, y un elemento y no en la lista, donde Y tiene aproximadamente 200 más pequeños que x - Cambiar X contra Y, agregue el elemento del tamaño 317. Incluso un algoritmo simple probablemente te encuentre buenas mejoras.

Un método completamente diferente: deje que la suma deseada sea S, con un S Muy grande (como muchos billones). Luego, puede elegir un S 'Decir alrededor de 1,000,000, multiplique todos los números involucrados por (S), encuentre elementos con una suma cerca de 1,000,000, y luego seleccione los artículos originales. Intente por unas pocas sumas que estén cerca de 1,000,000.

Answer 3

Gracias al comentario de @yuval, me llevaron al problema de la mochila que es exactamente lo que estaba buscando.

Aunque no entendí muchas de las soluciones propuestas a este problema completo de NP en Wikipedia, pensé en un enfoque rápido pero totalmente poco fiable:

Solo ordena la lista de enteros disponibles de los más pequeños a más grandes y comienzan a agregarlos hasta que se cumpla la condición deseada.

Creo que si todas las diferencias entre dos miembros del conjunto entero no varían mucho, entonces este enfoque probablemente le dará la mejor y única solución.