Wie finden Sie, welche Zahlen in einem Satz zu einer anderen bestimmten Anzahl aufaddieren?

Question

Hier ist ein Problem, das ich scheine in zu laufen mit einem Buchhaltungssystem zu arbeiten.

Ich habe eine Reihe von Transaktionen, aber ihre Summe nicht gleich den Betrag, der die Buchhaltung denkt, dass es sein sollte. Sie sind nicht die Mathematik in Frage, nur die Transaktionen enthalten sind: p

Gibt es einen Algorithmus, den mir, welche Transaktionen im Satz bestimmen würde dazu beitragen, sollte nicht für die Summe einbezogen werden, um eine bestimmte Menge zu entsprechen.

Given Set:  
2  
4  
5  
7

Given Sum Amount:
13

Result Set:
2
4
7

Edit: Es gibt weniger als 100 Transaktionen im Set. Hat jemand ein C # Beispiel hat, da es keine auf der ist Lösen der NP-vollständig Problem in XKCD Frage?

Mann, ich soll einen CS Grad bekommen.

Answer 1

Dies ist das Subset Sum Problem, das ist NP-Complete . Aber das bedeutet nicht, es ist nicht ein Algorithmus für eine Teilmenge Summe zu finden.

Answer 2

Dies ist das Knapsack Problem und es ist NP-vollständig. Sie werden es nicht leicht genau mit nichts außer kleinen Eingangssätze lösen. Für jedes anständiges Größe Problem Set, es ist einer von denen, Lebensdauer-of-the-Universum-to-Probleme zu lösen.

Das heißt, es sind Tornister genetischen Algorithmus Solver gibt.

Answer 3

Wie die oben genannten Elemente gesagt haben, ist dies der Subset-Sum Problem (oder Knapsackproblems). Um jedoch zu sagen, dass es nicht effizient durchgeführt werden kann, ist nicht sehr präzise. Es kann getan werden, nur nicht in polynomialer Zeit. Die Lösung ist eigentlich ganz einfach dynamische Programmierung mit und Rekursion (und in Pseudopolynomiell).

Bei ganzen Zahlen [a 1, ..., a_n] und eine Reihe T,

Definieren des Arrays S [i, k] zu bezeichnen, wenn es eine Teilmenge von Elementen ist zwischen a 1, ... a_i die summieren sich k. (Dies ist eine binäre Matrix).

Wir können dann eine rekursive Beziehung wie folgt definieren:

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

In Worten, dies bedeutet, dass wir entweder die Verwendung Element a_i oder wir tun es nicht. Die Antwort wird bei S angeordnet sein [n, T].

Was ist die Arbeitsbelastung Matrix S zu konstruieren? Nun, S hat n * T Elemente. Jedes Element zu berechnen, müssen wir O (1) arbeiten. So der gesamten Lauf Es ist O (n * T).

An diesem Punkt scheint es, dass ich P bewiesen haben = NP, da dies scheint ein Polynomialzeitalgorithmus zu sein. Beachten Sie jedoch, dass wir Eingangsgröße in binäre messen, so T = 2 ^ p für einige p.

Ich glaube nicht, dass jemand würde sagen, dass die oben genannte Lösung, wenn implementiert ist richtig unvernünftig. In der Tat für viele vernünftige Problemgrößen, wird es bewundernswert durchzuführen.

Auch gibt es einige Heuristik zur Lösung dieses Problems, aber ich bin kein Experte in diesem Bereich.

Answer 4

Dies ist eine Version von der Knapsackproblems . Es ist NP vollständig, so dass Sie nicht eine gute allgemeine Antwort in Gang zu bringen. Wie groß sind Ihre Sätze von Transaktionen? Ist es 5 wie Sie zeigte, oder ist es mehr wie 500?

Answer 5

OK. Viele Menschen haben den Namen des Problems gegeben und erwähnt, wie NP schwer es ist. Und in der Regel sind sie richtig. Sie haben jedoch einen ganz bestimmten Fall, dass Sie lösen müssen. Die erste Frage ist, ob Sie glauben, dass Ihre 100 Transaktionen sind in der Nähe, die richtigen zu sein. Sie haben einige total ( "Ihre" total). Sie haben etwas total. ( "Real" insgesamt). Einige Ihrer Transaktionen sind daher falsch. Wenn Sie vermuten, dass es dort nur wenige Scheingeschäfte sind, dann ist dies nicht so schlimm. Zum Beispiel wollen wir den Fall betrachten, wo es nur eine Schein-Transaktion ist. In diesem Fall würden wir nur 100 verschiedene Zahlen zu überprüfen. Wenn es zwei falsche trans, dann sind Sie auf der Suche bei 100 * 99 überprüft, und die Dinge werden bei 4 Schein trans, mit fast 100 Millionen Schritten verrückt. aber wenn alles tun Sie ist einige int der Zugabe, die nicht zu schrecklich ist.

Eine weitere mögliche Verknüpfung ist die Art Ihrer Daten zu untersuchen (nebenbei bemerkt, ist es möglich, die 100 „Zahlen“ und die erwartete Summe zu schreiben?). Wie viel ist Ihre Summe über die wirkliche Summe? Gibt es Werte so groß, dass sie beseitigen würde Ihre Summe plötzlich niedriger als die wirkliche Summe machen? Wenn ja, wissen Sie diese Werte nicht die falschen diejenigen sein können. Zum Beispiel, in Ihrem Beispiel 7 unbedingt erforderlich.

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

Ja, das ist möglich. Nicht sicher, ob dieser Beitrag noch geöffnet ist. Aber Sie wollen die Excel-Add-In Solver zu tun. Stellen Sie alle Zahlen, mit 1s auf der benachbarten Zelle. Dann legen Sie die Ausgangsnummer gewünscht .. dann alle verwendeten Zahlen, werden ihre benachbarten „1“ halten, während die nicht benutzten schaltet auf „0“. Dann machen Sie eine Filterformel, die nur diejenigen aufgelistet, die eine „1“ daneben haben.