Cómo encontrar una combinación de valores con una suma mayor pero más cercana a un objetivo

Answer 1

Un enfoque es utilizar el complemento Solver en Excel. Devolverá la combinación de valores más cercana al objetivo. Tenga en cuenta que esa combinación puede incluir más de dos números.

Configure el problema con una tabla de 3 columnas. La primera columna contiene sus números, la segunda es un valor entre 0 y 1 que inicialicé con 0, y la tercera contiene una fórmula que multiplica el valor de la primera columna por la segunda.

Luego agregue una celda con el valor objetivo y otra con la suma de los valores de la tercera columna. Finalmente, agregue una celda Objetivo con la fórmula que sea la suma objetivo menos la suma real. Luego devolví la combinación de valores como un grupo separado usando una fórmula ingresada en una matriz (requiere Excel 2016 con suscripción a Office 365 para la función TEXTJOIN):

= “{” & TEXTJOIN (“,”, TRUE, IF (C2: C7 = 0, “”, C2: C7)) & “}”

Finalmente, cargué el complemento Solver y le pedí que minimizara el valor de la celda Meta, sujeto a las restricciones de que los valores de la segunda columna sean binarios (0 o 1) y que la celda Meta sea mayor o igual a 0.

Si fuera a programar la solución, primero ordenaría los números en orden ascendente. Si solo buscara pares de valores, comenzaría con el número más grande que era menor que el objetivo y buscaría el otro número más grande que sea menor o igual a la diferencia entre el objetivo y el primer número. El resultado es un grupo separado, que almacenaría en una colección con su suma. Repita el proceso con números más pequeños. No es necesario probar ningún primer número que sea inferior a la mitad del objetivo. Ordenar la colección por los valores de suma asociados. Liste los resultados.

Answer 2

Este es un problema de programación de enteros, y es NP-hard (por reducción de 0,1 mochila). Como resultado, cualquier algoritmo existente para resolverlo podría tomar mucho tiempo para hacerlo.

En el lado positivo, los solucionadores existentes de ramificación y unión pueden ejecutarse en mucho menos tiempo del necesario para aplicar la fuerza bruta al intentar todas las combinaciones.

La IP en cuestión es:

[matemáticas] \ matemáticas {minimizar} \ sum a_ix_i [/ ​​matemáticas]

[math] a_i \ in \ mathbb {Z} \, [/ math] [math] \ mathrm {(dado)} [/ math]

[matemáticas] x_i \ in \ {0,1 \} [/ matemáticas]

[math] \ sum a_ix_i> T \, \ mathrm {(dado)} [/ math]