Gegeben sei eine Menge von n ganzen zahlen, die Liste aller möglichen Teilmengen mit Summe>=k

Gegeben eine unsortierte Menge der ganzen zahlen in form eines Arrays, finden Sie alle möglichen Teilmengen, deren Summe größer als oder gleich ein const integer k,
zB:- Unser set {1,2,3} und k=2

Möglichen Teilmengen:-

 {2},
 {3},
 {1,2},
 {1,3},
 {2,3}, 
 {1,2,3}

Ich denken kann, ein naiver Algorithmus, der eine Liste aller Teilmengen von set und überprüft, ob die Summe der Teilmenge ist >=k ist oder nicht, aber eine exponentielle Algorithmus und Auflistung aller Teilmengen erfordert O(2^N). Kann ich bei der dynamischen Programmierung lösen, die es in polynomieller Zeit?

  • Wenn Sie daran interessiert sind, drucken oder mit der Auflistung aller dieser Teilmengen, die dann im schlimmsten Fall können Sie immer noch 2^N-1 (alle außer leere) Teilmengen, die Sie brauchen, um Liste. Sie konnte jedoch zählen wie viele es sind, die mit dynamischer Programmierung in polynomieller.
  • Wie können wir die Anzahl solcher Teilmengen, die mit der dynamischen Programmierung?
  • Zu finden, wenn es eine Teilmenge, die Summen zu k ist NP-Hart (Subset Sum Problem) - also, diese Frage, wie auch. Und da willst du die aktuellen sets, scheint mir, dass brute Force Generierung aller Teilmengen ist der Weg zu gehen. (vielleicht fügen Sie einige Optimierungen unter Verwendung von branch-and-bound-Techniken, aber das ist über es, IMO)
  • Das Subset-Sum-Problem bezieht sich auf das finden einer Teilmenge, die Summen genau zu k, nicht mindestens k. Das finden einer Teilmenge, die Summen, um zumindest k ist O(n) (fügen Sie einfach alles-und sehen Sie, wenn die Summe groß genug ist).
  • Aber die Frage ist darum, ALLE Teilmengen, die größer/gleich k. Um dies zu tun, müssen Sie finden alle Teilmengen, die Summen zu k. Sie zu finden, ist NP-Schwer.
  • Sind Sie gerade auf der Suche nach einer Zählung aller Teilmengen, oder tatsächlich die Ausgabe der Menge von Teilmengen?
  • Wenn die zahlen positiv sind, Sie können prune gegen k - und max-Eingang. Wenn k<max, Pflaume alles >k. Wenn k>max prune jede wo in<max-k. Es ist immer noch exponentiell, aber n ist kleiner, das macht einen großen Unterschied in diesem Fall.
  • können Sie einige link, wo ich Lesen kann über den Ansatz, den Sie vorschlagen, im Grunde, wie zu lösen obiges problem, wenn die array-Größe ist klein (rund 40 Ganzzahlen), aber k ist eine große Anzahl

InformationsquelleAutor Hidetoshi | 2013-08-06
  1. 10

    Auflistung aller Teilmengen wird noch O(2^N) denn im schlimmsten Fall können Sie noch eine Liste aller Teilmengen abgesehen von der leere.

    Dynamische Programmierung kann Ihnen helfen, zählen die Anzahl der Sätze, die sum >= K

    Gehen Sie bottom-up verfolgen, wie viele Teilmengen summiert, um einen Wert aus dem Bereich [1..K]. Ein Ansatz, wie dies O(N*K) ist nur möglich für kleine K.

    Die Idee mit dem dynamischen Programmier-Lösung ist am besten mit einem Beispiel. Betrachten Sie diese situation. Nehme an, Sie wissen, dass aus all den sets bestehend aus der ersten i Elemente, die Sie wissen, dass t1 Summe 2 und t2 Summe 3. Lassen Sie uns sagen, dass die nächsten i+1 element ist 4. Alle vorhandenen sets können wir bauen alle neuen sets, die entweder durch anfügen des Elements i+1 oder verlassen Sie es aus. Wenn wir es weglassen, erhalten wir t1 Teilmengen, die Summe zu 2 und t2 Teilmengen, die Summe zu 3. Wenn wir Anhängen, dann erhalten wir t1 Teilmengen, die Summe zu 6 (2 + 4) und t2 diese Summe zu 7 (3 + 4) und eine Teilmenge, die enthält nur i+1 welche Summen 4. Das gibt uns die Anzahl von Teilmengen, die Summe zu (2,3,4,6,7) aus dem ersten i+1 Elemente. Wir fahren weiter bis N.

    In pseudo-code könnte dies so Aussehen:

    int DP[N][K];
int set[N];

//go through all elements in the set by index
for i in range[0..N-1]
   //count the one element subset consisting only of set[i]
   DP[i][set[i]] = 1

   if (i == 0) continue;

   //case 1. build and count all subsets that don't contain element set[i]
   for k in range[1..K-1]
       DP[i][k] += DP[i-1][k]

    //case 2. build and count subsets that contain element set[i]
    for k in range[0..K-1] 
       if k + set[i] >= K then break inner loop                     
       DP[i][k+set[i]] += DP[i-1][k]

//result is the number of all subsets - number of subsets with sum < K
//the -1 is for the empty subset
return 2^N - sum(DP[N-1][1..K-1]) - 1
    • Können Sie bitte mir sagen, wie dieses Teil --> Summe(DP[1...K]
    • Was ich damit meine, ist sum = DP[1] + DP[2] + .. + DP[K]
    • DP ist ein zwei-dimensionales array, also DP[0] + ... + DP[K] ist nicht wahr, dass ich denke,
    • Oh ja, entschuldigt, das ich nicht zahlen Aufmerksamkeit. sum = DP[N-1][1] + DP[N-1][2] + .. + DP[N-1][K-1]. Weil Sie versuchen herauszufinden, für sets, bestehend aus bis zu N (N-1 weil indiziert von 0), wie viele Summe entweder 1,2,3,..K-1. Wenn Sie herausfinden, wie viele, subtrahieren Sie diesen von allen Teilmengen zu bekommen, wie viele es sind, die Summe zu K, K+1 usw. Mein Fehler nicht erklären, es gut in den code.
    • Lassen Sie uns weiter, diese Diskussion im chat.
    InformationsquelleAutor cyon
  2. 6

    Kann ich verwenden Sie dynamische Programmierung, um es zu lösen in polynomialer Zeit?

    Nicht. Das problem ist sogar noch schwerer als @amit (in den Kommentaren) erwähnt. Finden, wenn es existiert eine Teilmenge, die Beträge zu einem bestimmten k ist die subset-sum-problem, die NP-schwer. Statt Sie zu Fragen, für wie viele Lösungen sind gleich auf eine bestimmte k, die in der viel schwierigeren Klasse von P#. Darüber hinaus ist Ihre genaue problem ist etwas schwieriger, da will man nicht nur zählen, sondern das auflisten aller möglichen Teilmengen für k und Zielen < k.

    InformationsquelleAutor Hooked
  3. 1

    Wenn k 0 ist, und jedes element des Satzes positiv ist dann haben Sie keine Wahl aber zu Ausgabe jede mögliche Teilmenge, so ist die untere Schranke für dieses problem ist O(2N) -- die Zeit, die zum erzeugen der Ausgabe.

    Es sei denn, Sie wissen, etwas mehr über den Wert k, die man noch nicht erzählte uns, gibt es keinen schnelleren Allgemeine Lösung, die eine überprüfung nur jede Teilmenge.

    InformationsquelleAutor Peter Alexander
Schreibe einen Kommentar