maximale Summe aus einer Teilmenge der Größe K mit Summe weniger als M

Question

Gegeben: Array von ganzen Zahlen Wert K, M

Frage: die maximale Summe finden, die wir von allen K Teilmengen von bestimmten Array erhalten so dass die Summe kleiner ist als der Wert M?

Gibt es für dieses Problem eine nicht dynamische Programmierlösung? oder wenn es nur dp [i] [j] [k] ist, kann nur diese Art von Problem lösen! können Sie bitte den Algorithmus erklären.

Answer 1

Dies ist eine Variante des Knapsack oder Subset-Problem, wo in Bezug auf die Zeit (auf Kosten der exponentiell wachsenden Platzanforderungen, wenn die Eingabegröße wächst), ist dynamische Programmierung die effizienteste Methode, die dieses Problem KORREKT löst. Eine ähnliche Frage zu Ihrer Frage finden Sie unter Is this variant of the subset sum problem easier to solve?.

Da jedoch Ihr Problem nicht genau das gleiche ist, werde ich trotzdem eine Erklärung liefern. Lassen Sie dp[i][j] = true, wenn es eine Teilmenge der Länge i gibt, die zu j und false summiert, wenn es nicht gibt. Die Idee ist, dass dp[][] die Summen aller möglichen Teilmengen für jede mögliche Länge codiert.Wir können dann einfach den größten j <= M finden, so dass dp[K][j]true ist. Unser Basisfall dp[0][0] = true, weil wir immer eine Teilmenge bilden können, die auf 0 aufsummiert, indem wir eine der Größe 0 auswählen.

Die Wiederholung ist auch ziemlich einfach. Angenommen, wir haben die Werte dp[][] unter Verwendung der ersten n Werte des Arrays berechnet. Um alle möglichen Teilmengen der ersten n+1 Werte des Arrays zu finden, können wir einfach den 0th-Wert nehmen und ihn zu allen Teilmengen hinzufügen, die wir vorher gesehen haben. Konkreter haben wir folgenden Code:

initialize dp[0..K][0..M to false 
dp[0][0] = true 
for i = 0 to N: 
    for s = 0 to K - 1: 
     for j = M to 0: 
      if dp[s][j] && A[i] + j < M: 
       dp[s + 1][j + A[i]] = true 
for j = M to 0: 
    if dp[K][j]: 
     print j 
     break 

Answer 2

Wir suchen nach einer Teilmenge von K Elementen, für die die Summe der Elemente maximal ist, aber weniger als M.

Wir können Grenzen [X, Y] auf dem größten Element in der Teilmenge wie folgt platzieren.

Zuerst sortieren wir die (N) Ganzzahlen, values[0] ... values[N-1], mit dem Element values[0] ist die kleinste.

Die untere Grenze X ist die größte ganze Zahl ist, für die

values[X] + values[X-1] + .... + values[X-(K-1)] < M.

(Wenn XN-1 ist, dann haben wir die Antwort gefunden.)

Die obere Grenze Y ist die größte ganze Zahl kleiner als N für die

values[0] + values[1] + ... + values[K-2] + values[Y] < M.

Mit dieser Beobachtung können wir gebunden jetzt den zweithöchste Begriff für jeden Wert des höchsten Begriffs Z, wo

X <= Z <= Y.

Wir können genau die gleiche Methode verwenden, da die Form des Problems genau gleich ist. Das reduzierte Problem besteht darin, eine Untermenge von K-1 Elementen aus values[0] ... values[Z-1] zu finden, für die die Summe der Elemente ein Maximum ist, aber weniger als M - values[Z].

Sobald wir den Wert in der gleichen Weise gebunden haben, können wir Grenzen auf den drittgrößten Wert für jedes Paar der beiden höchsten Werte setzen. Und so weiter.

Dies gibt uns eine Baumstruktur zu suchen, hoffentlich mit viel weniger Kombinationen als N suchen wählen K.

Answer 3

Felix ist richtig, dass dies ein Sonderfall des Rucksackproblems ist. Sein dynamischer Programmieralgorithmus nimmt die Größe der Zeit und die Größe (K * M) Größe und O (K * K * M). Ich glaube, dass seine Verwendung der Variablen N wirklich sein sollte K.

Es gibt zwei Bücher, die dem Rucksackproblem gewidmet sind. Der letzte von Kellerer, Pferschy und Pisinger [2004, Springer-Verlag, ISBN 3-540-40286-1] gibt einen verbesserten dynamischen Programmieralgorithmus auf ihrer Seite 76, Abbildung 4.2, die den Raum (K + M) einnimmt und O (KM) Zeit, was eine enorme Reduzierung im Vergleich zu dem von Felix gegebenen dynamischen Programmieralgorithmus ist. Beachten Sie, dass es in der letzten Zeile des Algorithmus einen Tippfehler gibt, wo es c-bar sein sollte: = c-bar - w_ (r (c-bar)).

Meine C# Implementierung ist unten. Ich kann nicht sagen, dass ich es ausführlich getestet habe, und ich begrüße das Feedback dazu. Ich habe verwendet, um das Konzept der Mengen zu implementieren, die in dem Algorithmus in dem Buch angegeben sind. In meinem Code c ist die Kapazität (die in der ursprünglichen Post M genannt wurde), und ich w anstelle von A als das Array, das die Gewichte enthält.

Ein Beispiel für seine Verwendung ist:

int[] optimal_indexes_for_ssp = new SubsetSumProblem(12, new List<int> { 1, 3, 5, 6 }).SolveSubsetSumProblem(); 

wo das Array optimal_indexes_for_ssp enthält [0,2,3] entsprechend den Elementen 1, 5, 6.

using System; 
using System.Collections.Generic; 
using System.Collections; 
using System.Linq; 

public class SubsetSumProblem 
{ 
    private int[] w; 
    private int c; 

    public SubsetSumProblem(int c, IEnumerable<int> w) 
    { 
     if (c < 0) throw new ArgumentOutOfRangeException("Capacity for subset sum problem must be at least 0, but input was: " + c.ToString()); 
     int n = w.Count(); 
     this.w = new int[n]; 
     this.c = c; 
     IEnumerator<int> pwi = w.GetEnumerator(); 
     pwi.MoveNext(); 
     for (int i = 0; i < n; i++, pwi.MoveNext()) 
     this.w[i] = pwi.Current; 
    } 

    public int[] SolveSubsetSumProblem() 
    { 
     int n = w.Length; 
     int[] r = new int[c+1]; 
     BitArray R = new BitArray(c+1); 
     R[0] = true; 
     BitArray Rp = new BitArray(c+1); 
     for (int d =0; d<=c ; d++) r[d] = 0; 
     for (int j = 0; j < n; j++) 
     { 
     Rp.SetAll(false); 
     for (int k = 0; k <= c; k++) 
      if (R[k] && k + w[j] <= c) Rp[k + w[j]] = true; 
     for (int k = w[j]; k <= c; k++) // since Rp[k]=false for k<w[j] 
      if (Rp[k]) 
      { 
      if (!R[k]) r[k] = j; 
      R[k] = true; 
      } 
     } 
     int capacity_used= 0; 
     for(int d=c; d>=0; d--) 
     if (R[d]) 
     { 
      capacity_used = d; 
      break; 
     } 
     List<int> result = new List<int>(); 
     while (capacity_used > 0) 
     { 
     result.Add(r[capacity_used]); 
     capacity_used -= w[r[capacity_used]]; 
     } ; 
     if (capacity_used < 0) throw new Exception("Subset sum program has an internal logic error"); 
     return result.ToArray(); 
    } 
}