完整的硬币组合搜索算法 [英] Complete search algorithm for combinations of coins
问题描述
该问题与硬币找零问题相似，但有一点不同。
问题描述为：您有一个硬币集合，并且您知道硬币的价值和其中每种硬币的数量。您想知道您可以从这些硬币的非空分组中获得多少不同的总和。
因此，例如 coins = [1， 2，3] 和数量= [1、2、2] ，有11种可能的总和，基本上所有的数字都是1-11。 / p>
数组硬币的长度最多只能增加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中计算 True将得到11。但是例如 coins = [10,50,100] 和 quantity = [1,2,1] 。答案是9个可能的总和，但如果使用子集总和，DP算法将获得21个真。如果基于[[10]，[50、100]，[100]]提供的列表是[10,50,100,100]或[10,50,100]
A python解决方案将是首选方法，但不是必需的。
下面是我当前的代码，在[10,50,100]硬币示例中得到21。
def可能的总和（硬币，数量）：
def子集总和（arr，s）：
dp = [False] *（s + 1 ）
dp [0] =真
for num in sorted（arr）：
for i in range（1，len（dp））：
如果num < = i：
dp [i] = dp [i]或dp [i-num]
返回总和（dp）
最大值=总和（ （map（lambda t：t [0] * t [1]，zip（硬币，数量））））
组合= [[]] len（硬币）
，c在枚举（硬币）中：
组合[i] = [j代表范围（c，（c * quantity [i]）+ 1，c）中的j]]
array = []
用于组合商品：
array.extend（item）
print（subsetSum（arr ay，maximum）-1）
保证约束：
1≤硬币。长度≤20，
1≤硬币[i]≤10 ^ 4。
数量。长度=硬币长度，
1≤数量[i]≤10 ^ 5。
保证（数量[0] +1）*（数量[1] +1） * ... *（quantity [quantity.length-1] +1）< = 10 ^ 6。
Bug修复
您的原始解决方案很好，只是您需要以相反的顺序进行迭代，以避免能够多次添加相同的硬币。
只需将内部循环更改为：
for num in sorted（arr）：$ b i在范围（len（dp）-1，-1，-1）中的$ b：如果num< = i：
dp [i] = dp [i]或dp [i- num]
更有效的解决方案
您也可以通过依次扫描每个可能的余数来利用具有相同价值的多个硬币来降低复杂性：
def PossibleSums2（硬币，数量）：
最大值= sum（（（map（lambda t：t [0] * t [1]，zip（硬币，数量）））））
dp = [假] * （最大值+ 1）
dp [0] =真
对于硬币，q在zip中（硬币，数量）：
对于b在范围（硬币）中：
num =- i在范围（b，最大+1，硬币）中的1
：如果dp [i]：
num = 0
elif num> = 0：
num + = 1
dp [i] = 0< = num <== q
print（sum（dp）-1）
这将具有O（最大*硬币）而不是O（最大*硬币*数量）
The problem is similar to coin change problem, but a little different.
The problem is stated as: You have a collection of coins, and you know the values of the coins and the quantity of each type of coin in it. You want to know how many distinct sums you can make from non-empty groupings of these coins.
So for example of coins = [1, 2, 3] and quantity = [1, 2, 2], there are 11 possible sums, basically all numbers from 1 - 11.
The length of the array coins can only go up to 20 but a quantity[x] can go up to 10^5.
What would be a possible algorithm solution that is efficient. Gathering all possible combinations of such a large quantity will take forever. Is there a mathematical formula that can determine the answer? I dont see how that it will work especially it wants distinct sums.
I was thinking of generating an array base on the coins and its quantity. Basically its multiple:
[ [1],
[2, 4],
[3, 6]]
Then have to select 1 or none from each of the arrays.
1
1,2
1,4
1,3
...
1,4,6
I cant seem to think of a good algorithm to perform that though. Doing nested loop might be too slow since there could be 20 different coins and each coin could have a large quantity.
Another possible solution is looping through 1 to maximum. Where maximum is the sum of all coins times its associated quantity. But the problem would be in determining if there exist a subset that will be equal to that number. I know there is a dynamic programming algorithm (subset sum) to determine if there exists a subset that will add up to a certain value, but what would be the array?
For this example it works fine, having the list as [1,2,4,3,6] and target sum is 11 then count the 'True' in DP will get 11. But for example coins = [10,50,100] and quantity = [1,2,1]. The answer is 9 possible sum but if using subset sum DP algo will get 21 'True'. If the list provided was [10,50,100,100] or [10,50,100] base on [[10], [50, 100], [100]]
A python solution would be preferred, but not necessary.
Below is my current code which got 21 for the [10,50,100] coins example.
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)
Guaranteed constraints:
1 ≤ coins.length ≤ 20,
1 ≤ coins[i] ≤ 10^4.
quantity.length = coins.length,
1 ≤ quantity[i] ≤ 10^5.
It is guaranteed that (quantity[0] + 1) * (quantity[1] + 1) * ... * (quantity[quantity.length - 1] + 1) <= 10^6.
Bug fix
Your original solution is fine, except that you need to iterate in reverse order to avoid being able to keep adding the same coin multiple times.
Simply change the inner loop to:
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]
More efficient solution
You can also reduce the complexity by taking advantage of the multiple coins with the same value by scanning up each possible remainder in turn:
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)
This will have complexity O(maximum * coins) instead of O(maximum * coins * quantity)
这篇关于完整的硬币组合搜索算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
