Question

VB算法问题，一个堆数字中凑出指定数字

希望能给一个比较高效的算法，可以说出原理，给个伪代码，我自己来实现

一堆数字的个数在20-30个左右，要求在这堆数字凑出一个指定的数字
比如从1、2、3、4、5...100中凑出和等于100的数字
1，99
2，88
1，2，97
等等，应该有很多，都属于正确结果

有点难，求助算法大神

Answer 1

这是个求子集合加总问题（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)
        Dim ra(ta_size - 1) As Integer 'differ from c/c++
        Array.Copy(ta, ra, ta_size)

        Dim converter = New Converter(Of Integer, String)(Function(num) num.ToString)
        Dim str = String.Join("+", Array.ConvertAll(ra, converter))

        lbSubset.Items.Add(str)
  End Sub
  
   Private Sub getSubsetSum(ByRef sa() As Integer, ByRef ta() As Integer,
                             ByVal sa_size As Integer, ByVal ta_size As Integer,
                             ByVal sum As Integer, ByVal cnt_node As Integer, ByVal target As Integer)
        Dim i As Integer

        If target = sum Then
            output(ta, ta_size)
            If cnt_node + 1 < sa_size And sum - sa(cnt_node) + sa(cnt_node + 1) <= target Then
                getSubsetSum(sa, ta, sa_size, ta_size - 1, sum - sa(cnt_node), cnt_node + 1, target)
            End If
            Return
        Else
            If cnt_node < sa_size And sum + sa(cnt_node) <= target Then
                For i = cnt_node To sa_size - 1 ' differ from c/c++
                    ta(ta_size) = sa(i)
                    If sum + sa(i) <= target Then
                        getSubsetSum(sa, ta, sa_size, ta_size + 1, sum + sa(i), i + 1, target)
                    End If
                Next i
            End If
        End If
    End Sub
    
    Private Sub generateSubsets(ByRef sa() As Integer, ByVal size As Integer, ByVal target As Integer)
        Dim ta(size - 1) As Integer
        Dim total As Integer = 0

        Array.Sort(sa)
        total = sa.Sum

        If (sa(0) <= target) And (total >= target) Then
            getSubsetSum(sa, ta, size, 0, 0, 0, target)
        End If
    End Sub
    
     Private Sub btnStart_Click(sender As System.Object, e As System.EventArgs) Handles btnStart.Click
        Dim size As Integer = 15
        Dim target As Integer = 10
        Dim data() As Integer
        Dim i As Integer

        lbSubset.Items.Clear()

        ReDim data(size - 1) 'differ from c/c++
        For i = LBound(data) To UBound(data)
            data(i) = i + 1
        Next i

        generateSubsets(data, size, target)
    End Sub

Answer 2

数据20-30个，这个高效与低效，运行时间应该差不了多少吧！
我给个简单的算法：
1，将这些数据读入一个数组a()
2，对数组内的数据进行升序排序
3，依次从数组中取一个数与其他数进行求和
1）先算两个数之和100的。从a(0)开始，当a(i)>50时，即可跳出循环，开始进行三个数之和是100的计算
2）当a(i)>34时，跳出循环，进行四个数之和是100的计算
3）当a(i)>25时，跳出循环，进行五个数之和是100的计算
依次类推

追问

我说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之后的数就不需要考虑了。

Answer 3

将一堆数字看成一个数组，从第一个开始，遍历剩下的数，如果第一个和第n个的和=100，就输出；遍历完后，从第二个在开始，遍历剩下的,如果第二个和第n个的和=100，...............

追问

这方法太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并不是固定的

如果你还是想说这样一个个循环下去，那就算了
说明你不懂算法啊