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)

数组是以0为基础的，计数可以是全局变量，并且visited是长度为2^n的数组。我知道这个问题具有指数复杂度，但是否有更好的方法/改进我的想法？该算法对于n≤24运行速度很快，但我的方法相当暴力，我在思考是否存在一些聪明的方法来找到例如n=30的答案。

- Atin

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!

- btilly