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!