Count-Kombinationen für 0-1 Rucksack

Question

Ich frage mich, was ist die effizienteste (Zeit und Speicher) Weg, um die Anzahl der Teilmengen mit der Summe kleiner oder gleich als ein Limit zu zählen. Zum Beispiel für die Menge {1, 2, 4} und die Grenze 3 sollte eine solche Zahl 4 sein (Teilmengen sind {}, {1}, {2}, {1, 2}). Ich habe versucht ein Teilmengen in einem Bit-Vektor-Codierung (Maske) und eine Antwort auf folgende Weise zu finden (Pseudocode):

solve(mask, sum, limit) 
    if visited[mask] 
    return 
    if sum <= limit 
    count = count + 1 
    visited[mask] = true 
    for i in 0..n - 1 
    if there is i-th bit 
     sum = sum - array[i] 
     mask = mask without i-th bit 
     count (mask, sum, limit) 
solve(2^n - 1, knapsack sum, knapsack limit) 

Arrays sind nullbasiert, Zählung eine globale Variable sein kann und visited ist ein Array von Länge 2^n. Ich verstehe, dass das Problem eine exponentielle Komplexität hat, aber gibt es eine bessere Annäherung/Verbesserung meiner Idee? Der Algorithmus läuft schnell für n ≤ 24, aber mein Ansatz ist ziemlich brutal und ich dachte über die Existenz eines cleveren Weg, um eine Antwort für n = 30 zum Beispiel zu finden.

Answer 1

Am effizientesten für Platz ist eine rekursive Traversierung aller Teilmengen, die nur zählt. Dies wird O(2^n) Zeit und O(n) Speicher wo n ist die Größe des gesamten Satzes.

Alle bekannten Lösungen können exponentiell in der Zeit sein, weil Ihr Programm eine Variation der Teilmenge-Summe ist. Dies ist bekannt als NP-vollständig. Aber eine ziemlich effiziente DP-Lösung ist im Pseudocode mit Kommentaren wie folgt.

# Calculate the lowest sum and turn all elements positive. 
# This turns the limit problem into one with only non-negative elements. 
lowest_sum = 0 
for element in elements: 
    if element < 0: 
     lowest_sum += element 
     element = -element 

# Sort and calculate trailing sums. This allows us to break off 
# the details of lots of ways to be below our bound. 
elements = sort elements from largest to smallest 
total = sum(elements) 
trailing_sums = [] 
for element in elements: 
    total -= element 
    push total onto trailing_sums 

# Now do dp 
answer = 0 
ways_to_reach_sum = {lowest_sum: 1} 
n = length(answer) 
for i in range(0, n): 
    new_ways_to_reach_sum = {} 
    for (sum, count) in ways_to_reach_sum: 
     # Do we consider ways to add this element? 
     if bound <= elements[i] + sum: 
      new_ways_to_reach_sum[sum] += count 

     # Make sure we keep track of ways to not add this element 
     if bound <= sum + trailing_sums[i]: 
      # All ways to compute the subset are part of the answer 
      answer += count * 2**(n - i) 
     else: 
      new_ways_to_reach_sum[sum] += count 
    # And finish processing this element. 
    ways_to_reach_sum = new_ways_to_reach_sum 

# And just to be sure 
for (sum, count) in ways_to_reach_sum: 
    if sum <= bound: 
     answer += count 

# And now answer has our answer!