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!