Algoritmo para encontrar os números de uma lista de tamanho n soma para outro número

Question

Eu tenho um número decimal (vamos chamá-lo objetivo ) e uma série de outros números decimais (vamos chamar o array elementos ) e eu preciso encontrar todas as combinações de números de elementos que soma a um golo.

Eu tenho uma preferência por uma solução em C # (.Net 2.0), mas pode o melhor algoritmo vitória independentemente.

A sua assinatura do método poderia ser algo como:

public decimal[][] Solve(decimal goal, decimal[] elements)

Answer 1

respostas interessantes. Obrigado por os ponteiros para Wikipedia - embora interessantes - eles realmente não resolver o problema como afirmado como eu estava à procura de correspondências exatas -. Mais de uma contabilidade / livro equilibrar problema do que um problema tradicional bin-packing / mochila

Tenho acompanhado o desenvolvimento de estouro de pilha com interesse e perguntou como seria útil. Este problema surgiu no trabalho e gostaria de saber se estouro de pilha pode fornecer uma resposta pronta (ou uma resposta melhor) mais rápido do que eu poderia escrever-me. Graças também para os comentários sugerindo esta lição de casa ser marcado - Eu acho que é razoavelmente precisa, à luz do acima

.

Para aqueles que estão interessados, aqui está a minha solução que usa recursão (naturalmente) Eu também mudei de idéia sobre a assinatura do método e fui para List> ao invés de decimal [] [] como o tipo de retorno:

public class Solver {

    private List<List<decimal>> mResults;

    public List<List<decimal>> Solve(decimal goal, decimal[] elements) {

        mResults = new List<List<decimal>>();
        RecursiveSolve(goal, 0.0m, 
            new List<decimal>(), new List<decimal>(elements), 0);
        return mResults; 
    }

    private void RecursiveSolve(decimal goal, decimal currentSum, 
        List<decimal> included, List<decimal> notIncluded, int startIndex) {

        for (int index = startIndex; index < notIncluded.Count; index++) {

            decimal nextValue = notIncluded[index];
            if (currentSum + nextValue == goal) {
                List<decimal> newResult = new List<decimal>(included);
                newResult.Add(nextValue);
                mResults.Add(newResult);
            }
            else if (currentSum + nextValue < goal) {
                List<decimal> nextIncluded = new List<decimal>(included);
                nextIncluded.Add(nextValue);
                List<decimal> nextNotIncluded = new List<decimal>(notIncluded);
                nextNotIncluded.Remove(nextValue);
                RecursiveSolve(goal, currentSum + nextValue,
                    nextIncluded, nextNotIncluded, startIndex++);
            }
        }
    }
}

Se você quiser um aplicativo para testar isso funciona, tente este código de console app:

class Program {
    static void Main(string[] args) {

        string input;
        decimal goal;
        decimal element;

        do {
            Console.WriteLine("Please enter the goal:");
            input = Console.ReadLine();
        }
        while (!decimal.TryParse(input, out goal));

        Console.WriteLine("Please enter the elements (separated by spaces)");
        input = Console.ReadLine();
        string[] elementsText = input.Split(' ');
        List<decimal> elementsList = new List<decimal>();
        foreach (string elementText in elementsText) {
            if (decimal.TryParse(elementText, out element)) {
                elementsList.Add(element);
            }
        }

        Solver solver = new Solver();
        List<List<decimal>> results = solver.Solve(goal, elementsList.ToArray());
        foreach(List<decimal> result in results) {
            foreach (decimal value in result) {
                Console.Write("{0}\t", value);
            }
            Console.WriteLine();
        }


        Console.ReadLine();
    }
}

Espero que isso ajude alguém obter a sua resposta mais rapidamente (seja para casa ou não).

Felicidades ...

Answer 2

O problema de soma subconjunto, eo problema ligeiramente mais geral mochila, são resolvidos com programação dinâmica: de força bruta enumeração de todas as combinações não é necessária. Consulte Wikipedia ou sua referência algoritmos favorito.

Embora os problemas são NP-completos, eles são muito "fácil" NP-completos. A complexidade algorítmica no número de elementos é baixa.

Answer 3

Eu acho que você tem um bin packing problema em suas mãos (que é NP -Hard), então eu acho que a única solução vai ser para tentar todas as combinações possíveis até encontrar um que funcione.

Edit: Como foi salientado em um comentário, você não vai sempre tem que tentar todas combinação para todas conjunto de números que vêm através. No entanto, qualquer método que você venha com tem conjuntos de pior caso de cenário de números onde irá tem que tentar todas combinação - ou, pelo menos, um subconjunto de combinações que cresce exponencialmente com o tamanho do conjunto.

Caso contrário, não seria NP-hard.

Answer 4

Você descreveu um mochila problema , a única verdadeira solução é a força bruta. Existem algumas soluções de aproximação que são mais rápidos, mas eles não podem atender às suas necessidades.

Answer 5

Enquanto não resolver o problema da força bruta (como outros já mencionado), você pode querer classificar os números em primeiro lugar, e, em seguida, passar por cima os possíveis esquerda (uma vez que uma vez que você passou valor Sum, você não pode adicionar qualquer número maior de Meta - Sum)

.

Isso vai mudar a maneira de implementar seu algoritmo (para tipo apenas uma vez e, em seguida, pular elementos marcados), mas, em média, iria melhorar o desempenho.

Answer 6

public class Logic1 {
    static int val = 121;
    public static void main(String[] args)
    {
        f(new int[] {1,4,5,17,16,100,100}, 0, 0, "{");
    }

    static void f(int[] numbers, int index, int sum, String output)
    {
        System.out.println(output + " } = " + sum);
        //System.out.println("Index value1 is "+index);
        check (sum);
        if (index == numbers.length)
        {
            System.out.println(output + " } = " + sum);
            return;
        }

        // include numbers[index]
        f(numbers, index + 1, sum + numbers[index], output + " " + numbers[index]);
        check (sum);
        //System.out.println("Index value2 is "+index);
        // exclude numbers[index]
        f(numbers, index + 1, sum, output);
        check (sum);
    }

    static void check (int sum1)
    {
        if (sum1 == val)
            System.exit(0);
    }
}