Como encontrar o que os números em um conjunto somam outro número dado?

Question

Aqui está um problema que me parece estar correndo para trabalhar com um sistema de contabilidade.

Eu tenho um conjunto de transações, mas sua soma não é igual ao montante que o departamento de contabilidade acha que deveria. Eles não estão questionando as contas, apenas as transações que estão sendo incluídos: p

Existe um algoritmo que iria me ajudar a determinar quais transações no conjunto não devem ser incluídos para que a soma para coincidir com um determinado montante.

Given Set:  
2  
4  
5  
7

Given Sum Amount:
13

Result Set:
2
4
7

Editar: Há menos de 100 transações no set. Alguém tem um exemplo de C #, como não há um na Resolvendo o NP-completos problema em XKCD pergunta?

Cara, eu deveria ter começado um grau CS.

Answer 1

Este é o problema subconjunto Sum , que é NP-Complete . Mas isso não significa que não há um algoritmo para encontrar uma soma subconjunto.

Answer 2

Esta é a Problema da Mochila e é NP-Completo. Você não vai facilmente resolvê-lo exatamente com qualquer coisa, exceto pequenos conjuntos de entrada. Para qualquer conjunto de problemas de tamanho decente, é um dos vida-of-the-universo-to-resolver problemas.

Dito isto, há genético-algoritmo solucionadores mochila lá fora.

Answer 3

Como os membros anteriores têm dito, este é o problema subconjunto Sum (ou problema da mochila). No entanto, para dizer que não pode ser feito de forma eficiente não é muito preciso. Isso pode ser feito, não apenas em tempo polinomial. A solução é bastante simples usando programação dinâmica e recursão (e em tempo pseudo-polinomial).

inteiros Dado [a_1, ..., a_n] e um número T,

Definir a matriz de S [i, k] para indicar se existe um subconjunto de elementos entre a_1, ... a_i que somam k. (Esta é uma matriz binária).

Podemos então definir uma relação recursiva como segue:

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

Em palavras, isso significa que qualquer uso elemento a_i ou não o fizermos. A resposta será localizado em S [N, T].

O que é a carga de trabalho para a construção de matriz S? Bem, S tem n * elementos T. Para calcular cada elemento, devemos fazer O (1) trabalho. Assim, a completa execução tempo é O (N * t).

Agora, neste momento, parece que eu tenho provado P = NP, pois isso parece ser um algoritmo de tempo polinomial. No entanto, lembre-se que medir o tamanho de entrada em binário, então T = 2 ^ p para alguns p.

Eu não acho que ninguém diria que a solução acima, quando implementado corretamente não é razoável. Na verdade, para muitos tamanhos razoáveis ??problema, ele irá realizar admiravelmente.

Além disso, existem algumas heurísticas para resolver este problema, mas eu sou não é um especialista na área.

Answer 4

Esta é uma versão do a mochila problema . É NP completo, para que você não está indo para obter uma boa resposta geral. Como grandes são seus conjuntos de transações? É 5 como se mostrou, ou é mais como 500?

Answer 5

OK. Muitas pessoas têm dado o nome do problema e mencionou como NP é difícil. E, em geral, eles estão corretos. No entanto, você tem um caso muito específico que você precisa resolver. A primeira pergunta a fazer é se ou não você acha que seus 100 transações estão perto de ser as mais acertadas. Você tem algum total ( "seu" total). Eles têm algum total. (Total "real"). Algumas de suas transações são, portanto, falso. Se você suspeitar que há apenas algumas transações fictícias em lá, então isso não é tão ruim. Por exemplo, vamos considerar o caso em que há apenas uma transação falsa. Nesse caso, só teria que verificar 100 números diferentes. Se houver 2 falso trans, então você está olhando para 100 * 99 cheques, e as coisas vão ficar loucos a 4 falso trans, com quase 100 milhões etapas. mas se tudo que você está fazendo é adicionar alguns de int que não é muito terrível.

Outra possível atalho é examinar a natureza dos seus dados (aliás, é possível postar os 100 "números" e a soma esperada?). Quanto é seu soma sobre a soma real? Existem quaisquer valores tão grande que eliminá-los faria sua soma repente menor do que a soma real? Se assim for, você sabe que esses valores não podem ser os únicos falsos. Por exemplo, no seu exemplo, 7 é absolutamente necessário.

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

Sim, isso é possível. Não tenho certeza se este post ainda está aberto. Mas você iria querer fazer o Excel Solver add-in. Post todos os números, com 1s na célula adjacente. Em seguida, coloque o número de saída desejado .. então todos os números usados, irão manter o seu lado "1", enquanto os não utilizados se voltarão para "0". Em seguida, faça uma fórmula filtro que apenas listas aqueles que têm um "1" ao lado dele.