Algoritmo para encontrar que los números de una lista de tamaño n suma a otro número

Question

Tengo un número decimal (vamos a llamar a objetivo y una variedad de otros números decimales (vamos a llamar a la matriz elementos) y necesito encontrar todas las combinaciones de números de elementos que se suma a la meta.

Tengo una preferencia por una solución en C# (.Net 2.0), pero puede que el mejor algoritmo de ganar independencia.

Su firma de método podría ser algo como:

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

Answer 1

Interesantes respuestas.Gracias por los punteros a Wikipedia - aunque interesante - que en realidad no resuelve el problema como se indicó como yo estaba buscando coincidencias exactas - más de una contabilidad/libro de equilibrio de problema que los de bin-packing / mochila problema.

He estado siguiendo el desarrollo de desbordamiento de pila con interés y se preguntó cuán útil sería.Este problema se acercó en el trabajo y me preguntaba si de desbordamiento de pila podría proporcionar una respuesta (o una mejor respuesta) más rápido de lo que yo podría escribir yo mismo.Gracias también por los comentarios que sugieren que este ser etiquetados de la tarea - supongo que es razonablemente precisa a la luz de las anteriores.

Para aquellos que estén interesados, aquí está mi solución que utiliza la recursividad (naturalmente) también he cambiado mi opinión acerca de la firma del método y se fue para la Lista> en lugar de decimal[][] como el tipo de valor devuelto:

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++);
            }
        }
    }
}

Si quieres una app para probar esto funciona, pruebe esta consola de código de la aplicación:

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 esto ayude a alguien más reciba su respuesta más rápida (ya sea para las tareas escolares o de otra manera).

Saludos...

Answer 2

El subconjunto de suma problema, y un poco más general del problema de la mochila, se resuelven con la programación dinámica:fuerza bruta enumeración de todas las combinaciones no es necesario.Consultar la Wikipedia, o su favorito de los algoritmos de referencia.

Aunque los problemas son NP-completos, son muy "fácil" NP-completo.La complejidad algorítmica en el número de elementos es baja.

Answer 3

Creo que tienes un bin problemas de embalaje en sus manos (que es NP-duro), así que creo que la única solución va a ser intentar todas las combinaciones posibles hasta encontrar uno que funcione.

Editar:Como se señaló en un comentario, no siempre tienen que probar cada combinación de cada conjunto de números que usted venir a través.Sin embargo, cualquier método que usted viene para arriba con el peor de los casos, los conjuntos de números donde se tienen que probar cada combinación-o al menos un subconjunto de las combinaciones que crece exponencialmente con el tamaño del conjunto.

De lo contrario, no sería NP-duro.

Answer 4

Se han descrito un mochila problema, la única solución verdadera es la fuerza bruta.Hay algunos aproximación de soluciones que son más rápidos, pero puede que no se ajuste a sus necesidades.

Answer 5

Mientras no resolver el problema de la fuerza bruta (como otros ya mencionados) es posible que desee ordenar los números, y luego ir a través de las posibles izquierda (ya que una vez pasado Suma del valor, no se puede agregar cualquier número mayor que la Meta de Suma).

Esto va a cambiar la forma de implementar el algoritmo (en el fin de ordenar sólo una vez y, a continuación, omita los elementos marcados), pero en promedio podría mejorar el rendimiento.

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);
    }
}