完整的硬币组合搜索算法

Question

问题类似于硬币变化问题,但有点不同.

问题表述为:你有一组硬币,你知道硬币的价值和每种硬币的数量.您想知道您可以从这些硬币的非空分组中获得多少不同的总和.

因此,例如coins = [1, 2, 3]和数量= [1, 2, 2],有11个可能的总和,基本上所有数字从1到11.

阵列硬币的长度最多只能达到20,但数量[x]最多可达10 ^ 5.

什么是有效的算法解决方案.收集如此大量的所有可能组合将需要永远.有没有可以确定答案的数学公式？我不知道它会如何工作,特别是它需要不同的总和.

我正在考虑根据硬币及其数量生成阵列.基本上是它的倍数:

[ [1],
  [2, 4],
  [3, 6]]

然后必须从每个阵列中选择1或不选.

1
1,2
1,4
1,3
...
1,4,6

我似乎无法想出一个好的算法来执行它.嵌套循环可能太慢,因为可能有20个不同的硬币,每个硬币可能有大量.

另一种可能的解决方案是循环1到最大值.最大值是所有硬币的总和乘以其相关数量.但问题在于确定是否存在将等于该数字的子集.我知道有一个动态编程算法(子集和)来确定是否存在将加起来某个值的子集,但是数组是什么？

对于这个例子它工作正常,列表为[1,2,4,3,6],目标总和为11然后计数DP中的'真'将得到11.但是例如coins = [10,50,100]和quantity = [1,2,1].答案是9可能的总和,但如果使用子集和DP算法将得到21'真'.如果根据[[10],[50,100],[100]提供的清单是[10,50,100,100]或[10,50,100]]

python解决方案将是首选,但不是必需的.

下面是我目前的代码,[10,50,100]硬币示例得到21.

def possibleSums(coins, quantity):
    def subsetSum(arr,s):
        dp = [False] * (s + 1)  
        dp[0] = True

        for num in sorted(arr):  
            for i in range(1, len(dp)):  
                if num <= i:  
                    dp[i] = dp[i] or dp[i - num]  
        return sum(dp)


    maximum = sum((map(lambda t: t[0] * t[1], zip(coins, quantity))))

    combinations = [[]]*len(coins)
    for i,c in enumerate(coins):
        combinations[i] = [ j for j in range(c,(c*quantity[i])+1,c) ]

    array = []
    for item in combinations:
        array.extend(item)

    print(subsetSum(array,maximum) - 1)

保证约束:

1 ? coins.length ? 20,
1 ? coins[i] ? 10^4.

quantity.length = coins.length,
1 ? quantity[i] ? 10^5.

保证(数量[0] + 1)*(数量[1] + 1)*...*(数量[quantity.length - 1] + 1)<= 10 ^ 6.

Answer 1

错误修复

您的原始解决方案很好,除了您需要以相反的顺序迭代以避免能够多次添加相同的硬币.

只需将内循环更改为:

    for num in sorted(arr):  
        for i in range(len(dp)-1,-1,-1):  
            if num <= i:  
                dp[i] = dp[i] or dp[i - num]

更高效的解决方案

您还可以通过依次扫描每个可能的剩余部分来利用具有相同值的多个硬币来降低复杂性:

def possibleSums2(coins, quantity):
    maximum = sum((map(lambda t: t[0] * t[1], zip(coins, quantity))))

    dp = [False] * (maximum + 1)
    dp[0] = True
    for coin,q in zip(coins,quantity):
        for b in range(coin):
            num = -1
            for i in range(b,maximum+1,coin):
                if dp[i]:
                    num = 0
                elif num>=0:
                    num += 1
                dp[i] = 0 <= num <= q

    print(sum(dp) - 1)

这将具有复杂度O(最大*硬币)而不是O(最大*硬币*数量)

Answer 2

不要收集所有组合,只收集总和.

您的集款项始于[0].一次一个地循环通过硬币.对于每个硬币,迭代其数量,将该倍数添加到集合中的每个项目.设置 - 将这些总和中的每一个添加到集合中.例如,让我们采用原始案例:coins = [1,2,3],quant = [1,2,2].走过这......

sum_set = {0}
current_coin  = 1;  #  coin[0]
current_quant = 1;  # quant[0]
This step is trivial ... add 1 to each element of the set.  This gives you {1}.
Add that to the existing set.  You now have
sum_set = {0, 1}

下一枚硬币:

current_coin  = 2;  #  coin[0]
current_quant = 2;  # quant[0]
Now, you have two items to add to each set element: 1*2, giving you {2, 3}; and 2*2, giving you {4, 5}.  
Add these to the original set:
sum_set = {0, 1, 2, 3, 4, 5}

最后的硬币:

current_coin  = 3;  #  coin[0]
current_quant = 2;  # quant[0]
You add 1*3 and 2*3 to each set element, giving you {3, 4, 5, 6, 7, 8} and {6, 7, 8, 9, 10, 11}.  
Adding these to the sum_set gives you the set of integers 0 through 11.

从集合中删除0(因为我们对该总和不感兴趣)并取出剩余集合的大小.11是你的答案.

这足以让你把它变成算法吗？我将把各种效率留给你.