环境：VB，重点是整理思路。
零、序
0.在ExcelHome上遇到很多凑数的贴子，粗略看过香川的代码，用的递归，看不懂，一直觉得这个比较难。春节无事，尝试挑战。
1.研习香川的贴子，花了很长时间，贴子里的解释不多，很费劲，主要是递归绕来绕去就绕晕了，最后发觉根本看不懂，放弃。
2.咨询老同学，点名这东西属于“背包问题”的简化版。
3.网上找了些背包的贴子，绝大多数都只有代码，关于解题思路说的太少，难以理解代码形成的过程。唯一一个有思路的贴子，用的全是数学符号，还是看不懂。
4.心得：看别人的代码比自己写代码还难。
5.不再看别人写的，打算自己硬编。
一、题型
有100张金额不等的发票，期望找到金额为1000元的各张发票的组合。
二、思路
（一）将发票按金额将序排列。
（二）简化问题：只找能够与第一张发票凑成1000的其他发票。
1st.FatherArr=发票集合，包含编号和金额；通过循环，使Arr=小于1000元的发票集合。
2nd.循环Arr，从第一张开始往下加：
1.如果金额小于1000，说明有希望凑成1000，将发票编号记录到临时变量（如ID），金额合计记录到临时变量（如Sum），然后接着加下一个。
2.如果金额等于1000，达成期望，把ID记录到结果数组（如Answer），搞定！
3.如果金额大于1000，失败，说明最后一次把数加冒了。
由于发票是降序排列，后面没准有可以能够与加冒之前凑成1000的票，但是怎么弄？
按照以上思路再循环一次！
只不过这次目标值变成1000-Sum，Arr是小于1000-Sum的发票集合。
3.1.如果金额小于1000-Sum，说明有希望凑成1000-Sum，将发票编号记录到临时变量（如ID），金额合计记录到临时变量（如Sum2），然后接着加下一个。
3.2.如果金额等于1000-Sum，达成期望，把ID记录到结果数组（如Answer），搞定！
3.3.如果金额大于1000-Sum，失败，说明最后一次把数加冒了。
由于发票是降序排列，后面没准有可以能够与加冒之前凑成1000-Sum的票，但是怎么弄？
按照以上思路再循环一次！
只不过这次目标值变成1000-Sum-Sum2，循环区域变成小于1000-Sum-Sum2的发票集合。
------------------------------------------------------------------------------------------------------------------------
从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事，讲的是：从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事……
------------------------------------------------------------------------------------------------------------------------
这TM不是圆环套圆环影视城吗，这TM不是递归吗？！这不就行了吗！就是不断的把Contral(i)切割成Contral(i+1)，不断的把Arr(i)切割成Arr(i+1)
3rd.回归原问题，按照此方法，再从第二张发票开始往下加，直到全轮一遍。
4th.以上为总体思路，过程中，除了调整Contral的值，另需调整Sum(n)；更重要的是切割Arr，并将用过的发票标记出来，从第x张发票开始轮的时候不再使用；在找到期望组合后，相关统计数据初始化。
5th.非常重要的一点：当通过递归1进入了递归2，在递归2完成或Exit Sub后，递归1入口后的代码还要继续执行，并不会因为完成递归N后，所有递归都结束，因此，最后一次递归结束后，无论是否找到期望值，相关统计数据都应当初始化。
（因为这个问题，中间耗费很大精力，一直没搞清楚各种变量是怎么变化的）
6th.过程中可以加点优化效率的代码。
三、代码
Sub Bag()
Dim Target: Target = 1000
Dim Arr: Arr = Sheets(1).UsedRange
Dim r: r = UBound(Arr)
Dim Answer: ReDim Answer(1 To r, 1 To 1) '结果标号集合
Dim SonArr '每次循环/递归以SonArr为基础，是Arr的子数组
Dim C: C = Target 'Contral，每次循环/递归后的目标值，是Target不断变小后形成的目标值；初始值为Target，每次循环后重新设置为Target
Dim S: S = 0 'Sum，小于Contral的值临时汇总于该变量；初始值为0，每次循环后重新设置为0
Dim ID: ID = "" '小于Contral的值的变号以连接符&拼接后临时存放于该变量；初始值为""，每次循环后重新设置为""
Dim k: k = 0 '符合拼凑条件的数的分组标号
Dim iFather '循环标签
For iFather = 1 To r '循环原理：每次从第r行截取Arr，定义为SonArr；断定SonArr里有没有符合拼凑条件的数。循环/递归过程中会对Arr进行调整，并以新的Arr进行截取。
ReDim SonArr(1 To r, 1 To 2)
For i = 1 To r - iFather + 1
SonArr(i, 1) = Arr(i + iFather - 1, 1)
SonArr(i, 2) = Arr(i + iFather - 1, 2)
Next
Call Dg(SonArr, C, S, ID, Answer, r, k, Arr, Target) '递归；符合拼凑条件的记录进Answer；SonArr\C\S\ID\Arr在递归过程中发生值变动
Next
With Sheets(1)
.Range("D:D").ClearContents
.[D1].Resize(r, 1) = Answer
End With
End Sub
Sub Dg(mySonArr, myC, myS, myID, theAnswer, r, k, theArr, theTarget)
'MsgBox mySonArr(1, 2) & vbTab & myC & vbTab & myS & vbTab & myID
If mySonArr(1, 2) = "#" Then Exit Sub '因为循环/递归过程中会对已用过的数以“#”标记，所以循环/递归时，先判断mySonArr第一个值是否为“#”，如果是就跳过去，提高效率
Dim Sp, p 'Sp为split-id后形成的数组，p为标号
Dim b: b = 0 'Brr实际有效值的数量
Dim Brr: ReDim Brr(1 To r, 1 To 2) '剔除大于C后的数的数组
t = 0
For i = 1 To r
If mySonArr(i, 2) <> "#" And mySonArr(i, 2) <= myC Then '符合条件的mySonArr的值记录进Brr；<注意C值在递归时要调整>；Brr实际有效值的数量为b
b = b + 1
Brr(b, 1) = mySonArr(i, 1)
Brr(b, 2) = mySonArr(i, 2)
t = t + Brr(b, 2)
End If
Next
If b = 0 Then Exit Sub '如果一个有效值都没有，结束递归
If t < myC Then Exit Sub '如果SUM(Brr)<Contral，说明所有值加起来都凑不够目标值，后续代码不必执行，量大时可提高效率
For i = 1 To b
Select Case myS + Brr(i, 2) '判定上一次合计值myS与新增值Brr(i, 2)的情况
Case Is < myC '如果该值小于Contral，则新增值记录进入myS\myID
myS = myS + Brr(i, 2)
myID = myID & "," & Brr(i, 1)
Case myC '如果该值等于Contral，则统计k，结果记录进入Answer，调整theArr，结束递归，临时统计变量初始化
myID = myID & "," & Brr(i, 1)
k = k + 1
Sp = Split(myID, ",")
For Each p In Sp
If p <> "" Then
theAnswer(Val(p), 1) = k
theArr(Val(p), 2) = "#"
End If
Next
myS = 0: myC = theTarget: myID = "": Exit Sub
Case Is > myC '如果该值大于Contral，则说明值冒了，将myC切割成小号myC，myS清零，并以小号myC再次递归
myC = myC - myS
myS = 0
Call Dg(Brr, myC, myS, myID, theAnswer, r, k, theArr, theTarget)
If myS = 0 And myC = theTarget And myID = "" Then Exit Sub
'<!！重要！!>因执行 Is > myC ，从大号递归进入小号递归的情况下，小号递归完成 Case myC 后，仍要返回大号递归继续完成 Is > myC 开始递归后的代码，因此，需要把临时统计数据初始化！并结束递归
End Select
Next
myID = "": myC = theTarget: myS = 0 '执行到这里，说明没找到符合条件的拼凑值，因此，初始化临时统计数据，为下一次循环/递归做准备
End Sub
四、感慨
中间不断调试，递来递去太乱了。
写完代码，发现竟然和香川的代码结构上差不多，也是醉了，这玩意果然只能自己写。
