Algorithmus, um die Zahlen aus einer Liste der Größe n Summe an eine andere Nummer zu finden

Question

Ich habe eine Dezimalzahl (nennen wir es Ziel ) und eine Reihe von anderen Dezimalzahlen (lassen Sie uns das Array aufrufen Elemente ) und ich brauche alle Kombinationen zu finden von Zahlen von Elementen welcher Summe Ziel.

Ich habe eine Vorliebe für eine Lösung in C # (.NET 2.0) kann aber der beste Algorithmus gewinnt unabhängig.

Ihre Methodensignatur könnte etwa so aussehen:

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

Answer 1

Interessante Antworten. Vielen Dank für die Hinweise auf Wikipedia - während interessant - sie nicht wirklich das Problem lösen, wie angegeben, wie ich nach genauen Übereinstimmungen gesucht -. Mehr einen Abrechnungs / Ausgleich Problem als ein herkömmliches bin-Verpackung / Knapsackproblems

Ich verfolge die Entwicklung von Stapelüberlauf mit Interesse und fragte sich, wie nützlich es sein würde. Dieses Problem trat bei der Arbeit, und ich fragte mich, ob Stack-Überlauf eine fertige Antwort (oder eine bessere Antwort) zur Verfügung stellen könnte schneller, als ich es selbst schreiben kann. Danke auch für die Kommentare diese Hausaufgabe wird getaggt was darauf hindeutet, - ich denke, dass in Anbetracht der obigen maßen genau ist

.

Für diejenigen, die interessiert sind, hier ist meine Lösung, die Rekursion verwendet (natürlich) Ich habe auch meine Meinung über die Methodensignatur und ging für List> anstatt dezimal [] [] als Rückgabetyp:

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

Wenn Sie eine App wollen dies funktioniert testen, versuchen Sie diese Konsole App-Code:

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

Ich hoffe, das jemand anderes hilft, ihre Antwort schneller (ob für Hausaufgaben oder auf andere Weise).

Prost ...

Answer 2

Das Subset-Sum Problem, und das etwas allgemeinere Knapsackproblems, mit dynamischer Programmierung gelöst: Brute-Force-Aufzählung aller Kombinationen ist nicht erforderlich. Consult Wikipedia oder Ihre bevorzugte Algorithmen Referenz.

Obwohl die Probleme sind NP-vollständig, sie sind sehr "easy" NP-vollständig. Die algorithmische Komplexität in der Anzahl der Elemente gering ist.

Answer 3

Ich glaube, Sie ein rel="nofollow Bin Packing Problem auf Ihre Hände haben (die NP -hard), so glaube ich, die einzige Lösung, jede mögliche Kombination sein wird, um zu versuchen, bis Sie eine finden, die funktioniert.

Edit: Wie in einem Kommentar darauf hingewiesen, werden Sie nicht immer müssen versuchen, alle Kombination für alle gesetzt Zahlen Sie kommen über. Jedoch kann jede Methode, die Sie kommen mit hat Worst-Case-Szenario Reihen von Zahlen, wo Sie wird müssen versuchen, alle Kombination - oder zumindest eine Teilmenge von Kombinationen, die wächst exponentiell mit der Größe des Satzes.

Ansonsten wäre es nicht NP-schwer.

Answer 4

Sie beschrieben haben, ein Knapsackproblems , ist die einzig wahre Lösung Brute-Force. Es gibt einige Näherungslösungen, die schneller sind, aber sie könnten Ihren Bedürfnissen passen.

Answer 5

Während das Problem der Brute-Force-Lösung (wie andere bereits erwähnt) Sie können Ihre Zahlen wollen zuerst sortieren, und gehen dann über die möglichen, links (da nach einer Sum-Wert übergeben, können Sie nicht eine beliebige Zahl größer hinzufügen als Ziel -. Sum)

Dies wird die Art und Weise ändern, die Sie Ihren Algorithmus implementieren (um nur einmal zu sortieren und dann markierte Elemente überspringen), aber im Durchschnitt würde die Leistung verbessern.

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