Ist diese Variante des Summenproblems der Untergruppe einfacher zu lösen?

StackOverflow https://stackoverflow.com/questions/376003

Frage

Ich habe ein Problem im Zusammenhang mit dem Summenproblem Und frage mich, ob die Unterschiede es einfacher machen, dh in angemessener Zeit lösbar.

Bei einem Wert V, einer festgelegten Größe L und einer Abfolge von Zahlen [1, n

Dies unterscheidet sich auf drei Arten von dem Problem der Teilmenge:

  1. Es ist mir wichtig, wie viele Untergruppen sind weniger als ein gegebener Wert, nicht wie viele sind gleich.
  2. Die Teilmengengrößen sind festgelegt.
  3. ich kümmre mich wie viele Legt Summe auf weniger als V fest, nicht nur, ob es irgendwelche existiert.

Gibt es einen einigermaßen effizienten Algorithmus, um dies zu lösen?

Bearbeiten: Offensichtlich kann dies in O (n wählen L) unter Verwendung eines Kombinationserzeugungsalgorithmus erfolgen. Was mich wirklich interessiert, sind clevere Hacks, um es erheblich zu beschleunigen.

War es hilfreich?

Lösung

(Die Entscheidungsversion von) Ihr Problem ist immer noch NP-Complete. Die Idee ist, dass wir, wenn wir Ihr Problem lösen könnten, (für jede Teilmengengröße) fragen könnten Sagen Sie uns, ob Teilmengen, die zu genau V Summe sind - daher könnten wir das Problem der Teilmenge lösen. [Dies ist kein vollständiger Beweis, weil es a ist Turing Reduktion, kein viele eine Reduktion.]

Es gibt jedoch einfache Dynamische Programmierung Lösung, die in der Zeit O (NLV) läuft. [Der Grund, warum dies nicht beweist, dass P = NP ist, dass V in der Eingangsgröße exponentiell sein könnte: Mit n Bits können Sie Werte bis 2 darstellenn. Aber unter der Annahme, dass Ihr V nicht exponentiell ist, ist dies kein Problem.

Num [v] [k] [i] bezeichnen die Anzahl der Größen-K-Untergruppen der ersten I-Elemente von S, die auf v. Sie können sie als (für jedes i) berechnen:

    num[0][0][i] = 1
    for v = 1 to V:
        for k = 1 to L:
            num[v][k][i] = num[v][k][i-1] + num[v-S[i]][k-1][i-1]

Wo s [i] das ITH -Element in Ihrer Sequenz ist. (Jeder Satz von Größe k, das zu V ist, verwendet entweder s [i], daher wird es in num [v] [k] [i-1] gezählt, oder es verwendet s [i], was bedeutet, dass der Rest von Die Untergruppe hat K-1-Elemente, verwendet nur die ersten I-1-Zahlen in der Sequenz und summen zu vs [i].) Schließlich zählen Sie num [v] [l] [| S |] für jedes V weniger als V ; Das ist deine Antwort.

Außerdem können Sie das dritte Index weglassen, wenn Sie es sorgfältig tun (Ihre Schleife für jedes i usw. ausführen). Ich habe es nur für Klarheit aufgenommen.

Andere Tipps

Ich bin nicht bereit, einen Beweis zu präsentieren, aber das klingt so, als ob er einem dynamischen Programmierschema zugänglich sein könnte Kleine Sammlung von Aussichten.

Eine Optimierung, die in den Sinn kommt, ist Folgendes: Bestellen Sie Ihre Sequenz (wenn es ALERADY nicht so ist). Wählen Sie die ersten L-1-Elemente von Anfang an und wählen Sie dann den letzten Artikel aus, dass es der größtmögliche Wert ist (der nächstgrößte Wert in der Sequenz würde eine Summe zu groß ergeben). Verwerfen Sie den Rest der Sequenz, da diese Elemente ohnehin niemals Teil einer gültigen Teilmenge sein können.

Danach denke ich, dass es wieder voll ist. Andererseits kann es auch andere Optimierungen möglich sein.

Die dynamische Programmierlösung für das Problem der Teilmenge generiert eine Tabelle, die diese Antwort enthält (dh eine boolesche Tabelle von V by n, wobei V die maximale Anzahl von Elementen ist und N die maximale Anzahl von Elementen ist, die sich in einem Satz befinden können, der die Befriedigung der Einschränkungen; jeder Boolesche ist wahr, wenn <= n Elemente zu <= V). Wenn n * v für Sie nicht zu groß ist, gibt es ein akzeptabel schneller Algorithmus. Die Untermenge -Summenlösung ist in dieser Tabelle nur das höchste festgelegte Element, für das die Anzahl der Elemente <= n/2 ist.

Wenn es sich nur um positive Ganzzahlen handelt, können Sie einen Überprüfungsschritt durchführen wenn Sie brauchen;

Nehmen Sie die Summe der kleinsten Zahlen der L-1 im Set. Wenn das eine Summe X ist, muss NX unter dem größten Element liegen, wenn das Problem ist soll eine Lösung haben. Kommen Sie, um darüber nachzudenken, Sie können andere L auf diese Weise beseitigen ...

Zum einen, da Sie Größe = l angeben, dann auch wenn Sie sich nichts Kluges vorstellen und nur Brute Force verwenden, werden Sie (n) im schlimmsten Fall getrennte Summen haben, also ist es ein bisschen besser als n ^^ l (gut, l+1, wie Sie dann jede Teilmenge summieren).

Dies klingt nach einer N -kategorie k -kategorie. Das Erzeugen von K-Subsets von N wird mit dem SKIENA-Algorithmus-Designhandbuch behandelt, und das Buch schlägt vor, relevante Teilmengen in lexikografischer Reihenfolge aufzählten (z. B. rekursiv). Machen Sie dann Ihre Summe und Ihren Vergleich in jeder Teilmenge.

Wenn Sie ein sortiertes Set haben, können Sie vermutlich unmögliche Lösungen aus dem Lösungsraum beschneiden.

Vielleicht ist die dynamische Programmierformulierung Amenamble zu einem PTAs von FPTAs.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top