¿Cómo encontrar qué números en un conjunto se suman a otro número dado?

Question

Este es un problema con el que parece que estoy trabajando para trabajar con un sistema de contabilidad.

Tengo un conjunto de transacciones, pero su suma no es igual a la cantidad que el departamento de contabilidad cree que debería. No cuestionan los cálculos, solo se incluyen las transacciones: p

¿Existe algún algoritmo que me ayude a determinar qué transacciones del conjunto no deben incluirse para que la suma coincida con un monto determinado?

Given Set:  
2  
4  
5  
7

Given Sum Amount:
13

Result Set:
2
4
7

Editar: Hay menos de 100 transacciones en el conjunto. ¿Alguien tiene un ejemplo de C # ya que no hay uno en Resolviendo el NP-completo problema en XKCD pregunta?

Hombre, debería haber obtenido un título de CS.

Answer 1

Este es el problema Suma de subconjuntos , que es NP-Complete . Pero eso no significa que no haya un algoritmo para encontrar una suma de subconjunto.

Answer 2

Este es el Problema de mochila y es NP-Completo. No lo resolverás fácilmente exactamente con nada excepto con pequeños conjuntos de entrada. Para cualquier conjunto de problemas de tamaño decente, es uno de esos problemas de toda la vida del universo para resolver.

Dicho esto, hay solucionadores de mochilas de algoritmo genético por ahí.

Answer 3

Como han dicho los miembros anteriores, este es el problema de la suma de subconjuntos (o el problema de la mochila). Sin embargo, decir que no se puede hacer de manera eficiente no es muy preciso. Se puede hacer, pero no En tiempo polinomial. La solución es bastante simple usando programación dinámica. y recursión (y en tiempo pseudo-polinomial).

Enteros dados [a_1, ..., a_n] y un número T,

Defina la matriz S [i, k] para indicar si hay un subconjunto de elementos entre a_1, ... a_i que suman k. (Esta es una matriz binaria).

Luego podemos definir una relación recursiva de la siguiente manera:

S [i, k] = S [i-1, k] o S [i-1, k-a_j]

En palabras, esto significa que o bien usamos el elemento a_i o no. La respuesta se ubicará en S [n, T].

¿Cuál es la carga de trabajo para construir la matriz S? Bueno, S tiene n * T elementos. Para calcular cada elemento, debemos hacer O (1) trabajo. Así que la ejecución completa el tiempo es O (n * T).

Ahora en este punto, parece que he probado P = NP, ya que esto Parece ser un algoritmo de tiempo polinomial. Sin embargo, recuerda que medimos el tamaño de entrada en binario, entonces T = 2 ^ p para algunos p.

No creo que nadie dijera que la solución anterior, cuando Implementado adecuadamente no es razonable. De hecho, para muchos tamaño razonable problema, se llevará a cabo admirablemente.

Además, hay algunas heurísticas para resolver este problema, pero estoy No soy un experto en esa área.

Answer 4

Esta es una versión de el problema de mochila . Es NP completo, así que no vas a obtener una buena respuesta general. ¿Qué tan grandes son sus conjuntos de transacciones? ¿Es 5 como mostraste, o es más como 500?

Answer 5

OK. Mucha gente ha dado el nombre del problema y mencionó lo difícil que es NP. Y en general, son correctos. Sin embargo, usted tiene un caso muy específico que necesita resolver. La primera pregunta que debe hacerse es si cree o no que sus 100 transacciones están cerca de ser las correctas. Tienes un total (" tu " total). Tienen algunos totales. (" real " total). Algunas de sus transacciones son, por lo tanto, falsas. Si sospechas que solo hay unas pocas transacciones falsas allí, entonces esto no es tan malo. Por ejemplo, consideremos el caso en el que solo hay una transacción falsa. En ese caso, solo tendríamos que verificar 100 números diferentes. Si hay 2 trans falsas, entonces estás viendo 100 * 99 cheques, y las cosas se volverán locas con 4 trans falsas, con casi 100,000,000 pasos. aunque si todo lo que estás haciendo es agregar algo de int, eso no es demasiado terrible.

Otro posible atajo es examinar la naturaleza de sus datos (por cierto, ¿es posible publicar los 100 números y la suma esperada?). ¿Cuánto es tu suma sobre la suma real? ¿Hay valores tan grandes que eliminarlos haría que su suma de repente sea más baja que la suma real? Si es así, sabes que esos valores no pueden ser los falsos. Por ejemplo, en su ejemplo, 7 es absolutamente necesario.

Answer 6

        bool bBreak = false;
        int iEnd = 13;
        ArrayList ar1 = new ArrayList();
        ar1.Add(2);
        ar1.Add(4);
        ar1.Add(5);
        ar1.Add(7);

        String s1 = " ";
        foreach (int i in ar1)
        {
            if (i == iEnd)
            {
                s1 = "Result = " + i;
                bBreak = true;
            }
            if (bBreak) break;
            ArrayList ar2 = new ArrayList();
            ar2.AddRange(ar1);
            ar2.Remove(i);
            foreach (int j in ar2)
            {
                if ((i + j) == iEnd)
                {
                    s1 = "Results = " + i + ", " + j;
                    bBreak = true;
                }

                if (bBreak) break;
                ArrayList ar3 = new ArrayList();
                ar3.AddRange(ar2);
                ar3.Remove(j);
                foreach (int k in ar3)
                {
                    if (bBreak) break;
                    if ((i + j + k) == iEnd)
                    {
                        s1 = "Results = " + i + ", " + j + ", " + k;
                        bBreak = true;
                    }
                }
            }
        }
        Console.WriteLine(s1);

Answer 7

Sí, esto es posible. No estoy seguro si esta publicación todavía está abierta. Pero usted querría hacer el complemento Excel Solver. Publicar todos los números, con 1s en la celda adyacente. Luego, coloque el número de salida deseado ... luego todos los números usados, mantendrán su " 1 " adyacente, mientras que los no utilizados se convertirán en " 0 " ;. Luego, haga una fórmula de filtro que muestre solo aquellos que tienen un " 1 " junto a ello.