子集和算法号码组中的重复 [英] Subset sum algorithm with repetition of numbers in the set
本文介绍了子集和算法号码组中的重复的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
予有含自然数和目标吨其是数字的组S.我想知道
我们怎样才能找到的这些号码这总计为靶T的可能的组合的数量。
若干可采取任何数量的时间和任何数目的数字可以采取用于获取在
总和等于目标万吨。
I have a set S containing natural numbers and a target t which is an number. I want to know
how can we find the number of possible combinations of these numbers which sums up to target t.
A number can be taken any number of times and any number of numbers can be taken for getting the
sum equal to the target t.
Example
target 6
Set s {3,8,1,2}
Solution 3+3, 3+2+1, 1+1+1+3, 2+2+2, 2+1+1+2, 2+1+1+1+1, 1+1+1+1+1+1
Total No of solutions possible 7
什么是有效的算法呢?
What can be the efficient algorithm for this?
推荐答案
如果目标是相当小的,可以用动态规划得到O(| S | * t)的解决方案。下面是一个示例code在Python:
If the target is reasonably small, you can use dynamic programming to obtain an O(|S| * t) solution. Here is a sample code in Python:
def combinations(S, t):
dp = [1] + [0] * t
for i in S:
for j in range(0, t - i + 1):
dp[j + i] += dp[j]
return dp[t]
这篇关于子集和算法号码组中的重复的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文