каких комбинации чисел в наборе добавить до заданных общих

Question

Я искал для решения одного математической задачи

У меня есть починки наборов чисел [65536, 131072, 262144, 524288, 104576, 2097152 ]

Я есть в общей сложности над числами только

, но моя проблема заключается в том, как я могу получить комбинацию цифр в данной сумме?

Пожалуйста, помогите мне плз

Answer 1

Интересный эксперимент мысли ... вот мое решение (предварительного предупреждения - нет кода, только алгоритм)

1. Заказать список по убыванию
2. использовать дерево/Структура узла
3. Напишите рекурсивный цикл, который перемещается по списку. Если значение, которое оно находится, меньше, чем оставшееся значение, добавьте это значение в качестве дочернего объекта
4. Если значение, которое оно равно, равно оставшемуся количеству, добавьте это значение в качестве дочернего элемента и отметьте как решение
5. если значение, что на это больше, чем остальные общей сложности, пометьте ветвь как не решаемой
6. IF конец списка будет достигнуто, отмечают, что отрасль не решаемая

Вы должны закончить с дерево, представляющее действительные решения. Пример:

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. вернуть все решения

Остерегайтесь: Я не понял, хотите ли вы использовать каждый номер набора только один раз для суммы, поэтому приведенный ниже код также рассчитает суммы, содержащие более одного экземпляра числа в данном наборе.
Если вы хотите, чтобы каждый номер появляться только один раз, найдите строку
Set result = AllSumsForTotalFromSet(total - number, numberSet, index, CopyAndReDimPlus1(partialSolution))
в функции Function AllSumsForTotalFromSet и заменить index с index-1 в рекурсивном вызове.

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