algorithm - 来自(可能非常大的)列表的非空分组的不同总和数

Question

假设给定了一组硬币类型(最多 20 种不同的类型)，并且每种类型最多有 10^5 个实例，这样列表中所有硬币的总数最多为 10^6。从这些硬币的非空分组中，您可以得出多少不同的总和。

for example, you are given the following lists:
coins=[10, 50, 100]
quantity=[1, 2, 1]
which means you have 1 coin of 10, and 2 coins of 50, and 1 coin of 100. 
Now the output should be
possibleSums(coins, quantity) = 9.

以下是所有可能的总和:

50 = 50;
10 + 50 = 60;
50 + 100 = 150;
10 + 50 + 100 = 160;
50 + 50 = 100;
10 + 50 + 50 = 110;
50 + 50 + 100 = 200;
10 + 50 + 50 + 100 = 210;
10 = 10;
100 = 100;
10 + 100 = 110.

如您所见，可以从硬币的非空分组中创建 9 个不同的总和。请注意，sum=110 的情况可以通过 50+50+10 或 100+10 得到，应该只计算一次。

我通过生成所有可能子集的列表并检查到目前为止生成的总和列表中是否存在每个子集的总和来解决这个问题。如果否，我会将总和添加到列表中并继续。

这是我编写的用于小列表的代码:

def possibleSums(coins, quantity):
    if coins is None: return None
    subsets = [[]]
    sums = set()
    next = []
    for coin, quant in zip(coins, quantity):
        for q in range(quant):
            for subs in subsets:
                s = sum(subs + [coin])
                if not s in sums:
                    next.append(subs + [coin])
                    sums.add(s)

            subsets += next
            next = []
    return len(subsets)-1

但是这种方法不适用于非常大的输入列表？例如:

coins = [1, 2]
quantity = [50000, 2]

这里需要生成2^50002个子集并检查它们对应的和，或者下面的例子:

coins = [1, 2, 3]
quantity = [2, 3, 10000]

我认为应该有一个不需要生成所有子集的解决方案，但我不知道应该如何解决。

有什么想法吗？

Answer 1

下一段代码使用动态规划来避免指数复杂度(而复杂度取决于可能的总和数和硬币数量)。我的 Python 技能较弱，因此可能会进行优化。

附言经典 DP 使用 length=1+所有硬币总和 的数组，这里我尝试使用集合。

def possibleSums(coins, quantity):
    sumset = set()
    tempset = set()
    sumset.add(0)
    for ic in range(len(coins)):
        coin = coins[ic]
        for q in range(quantity[ic]):
            val = (q + 1) * coin
            for s in sumset:
                if not (s + val) in sumset:
                    tempset.add(s+val)
        sumset = sumset | tempset
        tempset.clear()
    return len(sumset) - 1

print(possibleSums([3,5], [3,2]))
print(possibleSums([5,13,19], [10000,10,2]))