0-1揹包的計數組合

Question

我想知道最高效（時間和記憶）的方法來計算總和小於或等於某個限制的子集的數量。例如，對於集合{1, 2, 4}和極限3，這樣的數字應該是4（子集是{}, {1}, {2}, {1, 2}）。我想在一個位向量（掩模）編碼一子集，並在下列方式找到答案（僞碼）：

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) 

陣列是基於零的，計數可以是一個全局變量和visited是陣列長度爲2^n。我明白這個問題具有指數級的複雜性，但是對我的想法有更好的方法/改進嗎？該算法運行速度快爲n ≤ 24，但我的方法是非常蠻力的，並且我正在考慮存在一些巧妙的方法來找到n = 30的答案。

Answer 1

最有效的空間是所有子集的遞歸遍歷，只保留一個計數。這將是O(2^n)時間和O(n)內存，其中n是整個集合的大小。

所有已知的解決方案可以由於您的程序是子集和的變體，因此時間呈指數形式。這被稱爲NP完整。但一個非常有效的DP解決方案如下僞碼與評論。

# 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!