algorithm - 计数 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)

数组是从零开始的，count 可以是一个全局变量，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!