（可能非常大）列表的非空分组的总数不同 [英] Number of distinct sums from non-empty groupings of (possibly very large) lists
问题描述
硬币= [10,50,100]
数量= [1,2,1]
这意味着您有1枚10枚硬币和2枚50枚硬币以及1枚硬币100.
现在产量应该是
possibleSums（硬币，数量）= 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个不同的总和可以从您的硬币的非空分组创建。
请注意，总和= 110的情况可以通过50 + 50 + 10或100 + 10获得，应该只计算一次。
我接近通过生成所有可能子集的列表并检查每个子集的总和是否存在于生成的总和列表中来解决这个问题。如果不是，我会将总和添加到列表中并继续。
以下是我编写并使用小列表的代码：
def possibleSums（coins，quantity）：
如果硬币是None：return None
subsets = [[]]
sums = set（）
next = [ ]
为硬币，quant为zip（硬币，数量）：
为范围（quant）：
为子集中的子集：
s = sum（subs + [coin] ）
如果不是总和：
next.append（subs + [coin]）
sums.add（s）
subsets + = next
next = []
return len（subsets）-1
但是这种方法没有使用非常大的输入列表？例如：
硬币= [1,2]
数量= [50000，2]
需要生成2 ^ 50002个子集并检查其相应的总和，或者以下示例：
硬币= [1，2，3]
数量= [2,3,100]
我认为应该有一个解决方案，它不需要生成所有的子集，但我不知道应该如何解决它。
有什么想法？
下一个代码使用动态编程来避免指数复杂性（虽然复杂程度取决于可能的总数和硬币数量）。我的Python技能很弱，所以可能会进行优化。
Classic DP使用长度= 1 +所有硬币总金额的数组，在这里我尝试过使用set。
<$ p $
sumset = set（）
tempset = set（）
sumset.add（0）
for ic在范围内（len（硬币））：
coin =硬币[ic]
在范围内（数量[ic]）：
val =（q + 1）*硬币
在sumset中为s：
如果不是（s + val）在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]））
Assume that you are given a set of coin types (maximum 20 distinct types) and from each type you have maximum 10^5 instances, such that the total number of all the coins in your list is maximum 10^6. What is the number of distinct sums you can make from non-empty groupings of these coins.
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.
Here are all the possible sums:
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.
As you can see, there are 9 distinct sums that can be created from non-empty groupings of your coins. Notice that the case of sum=110 can be obtained by either 50+50+10 or 100+10 which should be counted only once.
I approached this problem by generating the list of all the possible subsets and checking if the sum of each subset exists in the list of generated sums so far. If no, I would add the sum to the list and proceed.
Here is the code that I've written and works with the small lists:
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
But this approach does not work with very large input list? For example:
coins = [1, 2]
quantity = [50000, 2]
where it needs to generate 2^50002 subsets and check their corresponding sums, or the following example:
coins = [1, 2, 3]
quantity = [2, 3, 10000]
I think that there should be a solution which doesn't require generating all the subsets, but I have no idea how it should be solved.
Any idea?
The next code uses dynamic programming to avoid exponential complexity (while complexity depends on the number of possible sums and coin quantity). My Python skills are weak, so optimizations might be possible.
P.S. Classic DP uses array of length=1+overall sum of all coins, here I tried with sets.
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]))
这篇关于（可能非常大）列表的非空分组的总数不同的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
