Count combinations for 0-1 knapsack

Question

I wonder what is the most efficent (time and memory) way to count the number of subsets with the sum less than or equal than some limit. For example, for the set {1, 2, 4} and limit of 3 such number whould be 4 (subsets are {}, {1}, {2}, {1, 2}). I tried coding a subsets in a bit vector (mask) and finding an answer in a following way (pseudo code):

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 are zero-based, count can be a global variable and visited is an array of length 2^n. I understand that the problem has an exponential complexity but is there a better approach/ improvement to my idea? The algorithm runs fast for n ≤ 24 but my approach is pretty brute-force and I was thinking about existance of some clever way to find an answer for n = 30 for instance.

user_585411 · Answer

The most efficient for space is a recursive traversal of all subsets that just keeps a count. This will be O(2^n) time and O(n) memory where n is the size of the overall set.

All known solutions can be exponential in time because your program is a variation of subset-sum. That is known to be NP complete. But a pretty efficient DP solution is as follows in pseudocode with comments.

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

Count combinations for 0-1 knapsack

1 Answers