希望能给一个比较高效的算法,可以说出原理,给个伪代码,我自己来实现
一堆数字的个数在20-30个左右,要求在这堆数字凑出一个指定的数字
比如从1、2、3、4、5...100中凑出和等于100的数字
1,99
2,88
1,2,97
等等,应该有很多,都属于正确结果
有点难,求助算法大神
这是个求子集合加总问题(subset sum problem)。是算法理论中比较有名的NP问题。
有几种经典解法:
1.组合论。 有所有集合元素的组合,然后求和与和目标比较。 方法简单,但算法复杂度高,当集合数较大,比如≥ 15后,速度明显慢;
2. 动态规划。递归求解,属于典型的divide and conquer方案。
3. 回溯法(backtracking),子集合属于这个里面的一个特例。 -- 虽然也要递归,但相较上面的方法,在集合比较大的时候,也能保持不错的效率。
下面给出回溯法的vb代码(vb 2010)。
Private Sub output(ByRef ta() As Integer, ByVal ta_size As Integer)我说1-100求100的和值只是一种特殊情况
实际是
一堆数据是未知的,只知道数据个数在20-30个左右
指定的求和值也是未知的
你疑问的地方是不是在a(i)>50,a(i)>34及a(i)>25
首先你要注意一点,所有这些数据(20-30个左右)是经过从小到大排序的,也就是说a(i)( sum/2+1)就可跳出循环了;同样道理,三个数之和为SUM,那么只要
a(i)>( sum/3+1)就可跳出循环了。
你想想,数据是从小到大排列的,当取到51时(假设和值是100),那么51跟比51大的任意值之和都会大于100,所以51之后的数就不需要考虑了。
这方法太2了
肯定有更高效的算法
Private Sub Command1_Click()
Dim arr As Variant
arr = Array(7, 2, 43, 4, 222)
For i = LBound(arr) To UBound(arr)
k = arr(i)
For j = i + 1 To UBound(arr)
If k + arr(j) = 6 Then
Text1.Text = str(k)
Text2.Text = arr(j)
End If
Next j
Next i
End Sub
这样很繁琐吗?!参考;
剩下的自己想吧;
我没有说只有2个数字的和啊- -!
我的例子中有3个数字的和,就意味着n个数字的和,这个n并不是固定的
如果你还是想说这样一个个循环下去,那就算了
说明你不懂算法啊