algorithm - repeticion - Averigüe qué combinaciones de números en un conjunto se suman a un total dado

demostracion combinaciones con repeticion

Question

Me han asignado la tarea de ayudar a algunos contadores a resolver un problema común que tienen: dada una lista de transacciones y un depósito total, ¿qué transacciones forman parte del depósito? Por ejemplo, digamos que tengo esta lista de números:

1.00
2.50
3.75
8.00

Y sé que mi depósito total es de 10.50 , puedo ver fácilmente que está compuesto por la transacción de 8.00 y 2.50 . Sin embargo, dado un centenar de transacciones y un depósito en millones, rápidamente se vuelve mucho más difícil.

Al probar una solución de fuerza bruta (que lleva demasiado tiempo para ser práctica), tuve dos preguntas:

1. Con una lista de alrededor de 60 números, parece encontrar una docena o más combinaciones para cualquier total que sea razonable. Esperaba que una combinación única satisficiera mi total, o quizás algunas posibilidades, pero siempre parece haber un montón de combinaciones. ¿Hay un principio matemático que describa por qué esto es? Parece que dada una colección de números aleatorios de incluso un tamaño mediano, puede encontrar una combinación múltiple que se suma a casi cualquier total que desee.

2. Construí una solución de fuerza bruta para el problema, pero es claramente O (n!), Y rápidamente se sale de control. Aparte de los atajos obvios (excluye números más grandes que el total en sí), ¿hay alguna forma de acortar el tiempo para calcular esto?

Detalles sobre mi solución actual (super-lenta):

La lista de cantidades detalladas se clasifica de mayor a menor, y luego el siguiente proceso se ejecuta de forma recursiva:

• Tome el siguiente elemento de la lista y vea si sumarlo a su total acumulado hace que su total coincida con el objetivo. Si lo hace, ponga a un lado la cadena actual como un partido. Si no alcanza su objetivo, agréguelo a su total acumulado, elimínelo de la lista de cantidades detalladas y luego vuelva a llamar a este proceso

De esta manera, excluye los números más grandes rápidamente, reduciendo la lista a solo los números que necesita considerar. Sin embargo, todavía es n! y parece que las listas más grandes nunca terminan, por lo que me interesan los accesos directos que podría tomar para acelerar esto. Sospecho que incluso cortar un número de la lista reduciría el tiempo de cálculo a la mitad.

¡Gracias por tu ayuda!

Answer 1

Dependiendo de sus datos, primero puede ver la porción de centavos de cada transacción. Como en su ejemplo inicial, usted sabe que 2.50 tiene que ser parte del total porque es el único conjunto de transacciones de centavos que no son cero y que se suman a 50.

Answer 2

El Excel Solver Addin publicado en superuser.com tiene una excelente solución (si tiene Excel) https://superuser.com/questions/204925/excel-find-a-subset-of-numbers-that-add-to-a-given-total

Answer 3

Es una especie de problema de mochila 0-1 que es NP-completo y puede resolverse mediante programación dinámica en tiempo polinomial.

knapsack

Pero al final del algoritmo también debe comprobar que la suma es lo que quería.

Answer 4

Este caso especial del problema Knapsack se llama Subset Sum .

Answer 5

Hay un complemento de Excel barato que resuelve este problema: SumMatch

Answer 6

No es una solución súper eficiente, pero tiene una implementación en coffeescript

combinations devuelve todas las combinaciones posibles de los elementos en la list

combinations = (list) ->
        permuations = Math.pow(2, list.length) - 1
        out = []
        combinations = []

        while permuations
            out = []

            for i in [0..list.length]
                y = ( 1 << i )
                if( y & permuations and (y isnt permuations))
                    out.push(list[i])

            if out.length <= list.length and out.length > 0
                combinations.push(out)

            permuations--

        return combinations

y luego find_components lo usa para determinar qué números se suman al total

find_components = (total, list) ->
    # given a list that is assumed to have only unique elements

        list_combinations = combinations(list)

        for combination in list_combinations
            sum = 0
            for number in combination
                sum += number

            if sum is total
                return combination
        return []

Heres un ejemplo

list = [7.2, 3.3, 4.5, 6.0, 2, 4.1]
total = 7.2 + 2 + 4.1

console.log(find_components(total, list)) 

el cual devuelve [ 7.2, 2, 4.1 ]

Answer 7

Si entiendo su problema correctamente, usted tiene un conjunto de transacciones y simplemente desea saber cuál de ellas podría haber sido incluida en un total dado. Entonces, si hay 4 transacciones posibles, entonces hay 2 ^ 4 = 16 conjuntos posibles para inspeccionar. Este problema es que, para 100 transacciones posibles, el espacio de búsqueda tiene 2 ^ 100 = 1267650600228229401496703205376 combinaciones posibles para buscar. Para 1000 transacciones potenciales en la mezcla, crece a un total de

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

conjuntos que debes probar. La fuerza bruta difícilmente será una solución viable para estos problemas.

En su lugar, use un solucionador que pueda manejar problemas de knapsack . Pero incluso entonces, no estoy seguro de que pueda generar una enumeración completa de todas las soluciones posibles sin una variación de la fuerza bruta.

Answer 8

Versión C #

prueba de configuración

using System;
using System.Collections.Generic;

public class Program
{
    public static void Main(string[] args)
    {
    // subtotal list
    List<double> totals = new List<double>(new double[] { 1, -1, 18, 23, 3.50, 8, 70, 99.50, 87, 22, 4, 4, 100.50, 120, 27, 101.50, 100.50 });

    // get matches
    List<double[]> results = Knapsack.MatchTotal(100.50, totals);

    // print results
    foreach (var result in results)
    {
        Console.WriteLine(string.Join(",", result));
    }

    Console.WriteLine("Done.");
    Console.ReadKey();
    }
}

código:

using System.Collections.Generic;
using System.Linq;

public class Knapsack
{
    internal static List<double[]> MatchTotal(double theTotal, List<double> subTotals)
    {
    List<double[]> results = new List<double[]>();

    while (subTotals.Contains(theTotal))
    {
        results.Add(new double[1] { theTotal });
        subTotals.Remove(theTotal);
    }

    // if no subtotals were passed
    // or all matched the Total
    // return
    if (subTotals.Count == 0)
        return results;

    subTotals.Sort();

    double mostNegativeNumber = subTotals[0];
    if (mostNegativeNumber > 0)
        mostNegativeNumber = 0;

    // if there aren''t any negative values
    // we can remove any values bigger than the total
    if (mostNegativeNumber == 0)
        subTotals.RemoveAll(d => d > theTotal);

    // if there aren''t any negative values
    // and sum is less than the total no need to look further
    if (mostNegativeNumber == 0 && subTotals.Sum() < theTotal)
        return results;

    // get the combinations for the remaining subTotals
    // skip 1 since we already removed subTotals that match
    for (int choose = 2; choose <= subTotals.Count; choose++)
    {
        // get combinations for each length
        IEnumerable<IEnumerable<double>> combos = Combination.Combinations(subTotals.AsEnumerable(), choose);

        // add combinations where the sum mathces the total to the result list
        results.AddRange(from combo in combos
                 where combo.Sum() == theTotal
                 select combo.ToArray());
    }

    return results;
    }
}

public static class Combination
{
    public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int choose)
    {
    return choose == 0 ?                        // if choose = 0
        new[] { new T[0] } :                    // return empty Type array
        elements.SelectMany((element, i) =>     // else recursively iterate over array to create combinations
        elements.Skip(i + 1).Combinations(choose - 1).Select(combo => (new[] { element }).Concat(combo)));
    }
}

resultados:

100.5
100.5
-1,101.5
1,99.5
3.5,27,70
3.5,4,23,70
3.5,4,23,70
-1,1,3.5,27,70
1,3.5,4,22,70
1,3.5,4,22,70
1,3.5,8,18,70
-1,1,3.5,4,23,70
-1,1,3.5,4,23,70
1,3.5,4,4,18,70
-1,3.5,8,18,22,23,27
-1,3.5,4,4,18,22,23,27
Done.

Si se repiten los subtotales, aparecerán resultados duplicados (el efecto deseado). En realidad, es probable que desee utilizar el SubTotal Tupled con algún ID, para que pueda relacionarlo con sus datos.