其中一組數字的組合加起來給定的總

Question

我一直在尋找一個數學問題的解決

我有固定組數字 [65536，131072，262144，524288，104576的，2097152 ]

我會有一些總以上數字僅

的，但我的問題是，我怎樣才能在給定的總數字的組合？

請幫我PLZ

Answer 1

有趣的思想實驗......這裏是我的解決方案（預警 - 沒有代碼，只有算法）

1. 順序列表降
2. 使用樹/節點結構
3. 編寫遍歷列表的遞歸循環。如果它所在的值小於剩餘值，則將該值作爲孩子添加
4. 如果它的值等於剩餘的總和，則將該值作爲孩子添加並標記爲解決方案
5. 如果它是在比總剩餘更大的價值，標誌着分公司爲不可解
6. 如果達到列表的末尾，標誌着該分支爲不可解

您應該結束了代表有效解決方案的樹。例如：

set = [50,40,30,20,15,10,5] 
total required = 60 
Solution tree 
root 
    50 -> 10 
    40 -> 20 
     -> 15 -> 5 
    30 -> 20 -> 10 
     -> 15 -> 10 -> 5 

Answer 2

我的解決方案與Davids非常相似。

假設：該組數字是按照升序排列的。

調用該函數並從最高數字開始，傳遞一個空的部分解決方案，並嘗試計算返回總數的一組數字的所有可能總和。這些款項以集合形式返回。

功能：

1. 創建一個列表來保存所有的解決方案
2. 試驗組中的每個數字（從傳遞numberSetIndex和向下移動）：
   1. 如果number > total然後跳到下一個號碼
   2. 將該號碼附加到部分解決方案
   3. if number = total然後將此部分解決方案添加到列表並重新移動到下一個數字
   4. 如果number < total然後
      1. 調用這個函數（total -= number和部分解決方案的副本，並與數的當前索引）
      2. 追加所有返回的解決方案
3. 回報所有的解決方案

小心：我不明白，如果你想使用集合中的每個數字只有一次總和，所以下面的代碼也會計算包含給定集合中多個數字實例的總和。
如果希望每個號碼只出現一次，定位功能Function AllSumsForTotalFromSet行
Set result = AllSumsForTotalFromSet(total - number, numberSet, index, CopyAndReDimPlus1(partialSolution))
和遞歸調用與index-1取代index。

Sub Test_AllSumsForTotalFromSet() 
    Dim numberSet, total As Long, result As Collection 

    numberSet = Array(65536, 131072, 262144, 524288, 104576, 2097152) 
    total = 366720 

    Set result = GetAllSumsForTotalFromSet(total, numberSet) 

    Debug.Print "Possible sums: " & result.count 

    PrintResult result 
End Sub 

Function GetAllSumsForTotalFromSet(total As Long, ByRef numberSet As Variant) As Collection 
    Set GetAllSumsForTotalFromSet = New Collection 
    Dim partialSolution(1 To 1) As Long 

    Set GetAllSumsForTotalFromSet = AllSumsForTotalFromSet(total, numberSet, UBound(numberSet), partialSolution) 
End Function 

Function AllSumsForTotalFromSet(total As Long, ByRef numberSet As Variant, numberSetIndex As Long, ByRef partialSolution() As Long) As Collection 
    Dim index As Long, number As Long, result As Collection 

    Set AllSumsForTotalFromSet = New Collection 

    'break if numberSetIndex is too small 
    If numberSetIndex < LBound(numberSet) Then Exit Function 

    For index = numberSetIndex To LBound(numberSet) Step -1 
     number = numberSet(index) 

     If number <= total Then 
      'append the number to the partial solution 
      partialSolution(UBound(partialSolution)) = number 

      If number = total Then 
       AllSumsForTotalFromSet.Add partialSolution 

      Else 
       Set result = AllSumsForTotalFromSet(total - number, numberSet, index, CopyAndReDimPlus1(partialSolution)) 
       AppendCollection AllSumsForTotalFromSet, result 
      End If 
     End If 
    Next index 
End Function 

'copy the passed array and increase the copy's size by 1 
Function CopyAndReDimPlus1(ByVal sourceArray As Variant) As Long() 
    Dim i As Long, destArray() As Long 
    ReDim destArray(LBound(sourceArray) To UBound(sourceArray) + 1) 

    For i = LBound(sourceArray) To UBound(sourceArray) 
     destArray(i) = sourceArray(i) 
    Next i 

    CopyAndReDimPlus1 = destArray 
End Function 

'append sourceCollection to destCollection 
Sub AppendCollection(ByRef destCollection As Collection, ByRef sourceCollection As Collection) 
    Dim e 
    For Each e In sourceCollection 
     destCollection.Add e 
    Next e 
End Sub 

Sub PrintResult(ByRef result As Collection) 
    Dim r, a 

    For Each r In result 
     For Each a In r 
      Debug.Print a; 
     Next 
     Debug.Print 
    Next 
End Sub