給定一組數字：{1、3、2、5、4、9}，找到合計為特定值的子集數量（例如，本示例為9）。這類似于子集總和問題，只是存在細微差異，而不是檢查集合是否有一個總和為9的子集，我們必須找到此類子集的數量。我在這里關注子集和問題的解決方案 。但是，我想知道如何修改它以返回子集的計數。
3 回答
慕哥6287543
TA貢獻1831條經驗 獲得超10個贊
def total_subsets_matching_sum(numbers, sum):
array = [1] + [0] * (sum)
for current_number in numbers:
for num in xrange(sum - current_number, -1, -1):
if array[num]:
array[num + current_number] += array[num]
return array[sum]
assert(total_subsets_matching_sum(range(1, 10), 9) == 8)
assert(total_subsets_matching_sum({1, 3, 2, 5, 4, 9}, 9) == 4)
說明
這是經典問題之一。這個想法是用當前數量找到可能的總和數量。確實，只有一種方法可以將總和設為0。一開始，我們只有一個數字。我們從目標（解決方案中的變量最大值）開始，然后減去該數字。如果有可能獲得該數字的和（與該數字對應的數組元素不為零），則將其添加到與當前數字對應的數組元素中。該程序將更容易理解這種方式
for current_number in numbers:
for num in xrange(sum, current_number - 1, -1):
if array[num - current_number]:
array[num] += array[num - current_number]
當數字為1時，只有一種方法可以得出總和1（1-1變?yōu)?且對應于0的元素為1）。因此，數組將像這樣（記住元素零將具有1）
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
現在，第二個數字為2。我們開始從9中減去2，并且它是無效的（由于7的數組元素為零，因此我們跳過了這一點），直到3為止。當其3、3-2為1且數組元素為對應于1的是1，然后將其添加到3的數組元素中。當其2、2-2變?yōu)?時，我們將對應于0的值添加到2的數組元素中。在此迭代之后，數組看起來像這樣
[1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
我們一直這樣做，直到每次迭代后處理所有數字和數組都像這樣
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 2, 1, 1, 1, 0, 0, 0]
[1, 1, 1, 2, 2, 2, 2, 2, 1, 1]
[1, 1, 1, 2, 2, 3, 3, 3, 3, 3]
[1, 1, 1, 2, 2, 3, 4, 4, 4, 5]
[1, 1, 1, 2, 2, 3, 4, 5, 5, 6]
[1, 1, 1, 2, 2, 3, 4, 5, 6, 7]
[1, 1, 1, 2, 2, 3, 4, 5, 6, 8]
在最后一次迭代之后，我們將考慮所有數字，并且獲得目標的方法數量將是與目標值相對應的數組元素。在我們的例子中，最后一次迭代后的Array [9]為8。
萬千封印
TA貢獻1891條經驗 獲得超3個贊
您可以使用動態(tài)編程。算法復雜度為O（Sum * N），并使用O（Sum）內存。
這是我在C＃中的實現：
private static int GetmNumberOfSubsets(int[] numbers, int sum)
{
int[] dp = new int[sum + 1];
dp[0] = 1;
int currentSum =0;
for (int i = 0; i < numbers.Length; i++)
{
currentSum += numbers[i];
for (int j = Math.Min(sum, currentSum); j >= numbers[i]; j--)
dp[j] += dp[j - numbers[i]];
}
return dp[sum];
}
注意：由于子集數可能具有2 ^ N的值，因此很容易會溢出int類型。
算法僅適用于正數。
添加回答
舉報
0/150
提交
取消