Найти все комбинации чисел из массива, чтобы достичь заданной суммы

Question

Я учусь vb.net , поэтому я много искал об этом, но не смог найти решение.

У меня есть массив:

{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536}

Как можно видеть, это следующая 2^n последовательность.

Как получить все массивы, в которых сумма соответствует заданному значению ОПТИМИЗИРОВАННЫМ способом?

Примеры:

1. Сумма: 64 -> Результат: {64}
2. Сумма: 80 -> Результат: {16, 64} или {64, 16} (только один из этих массивов)
3. Сумма: 162 -> Результат: {128, 32, 2}

Answer 1

Альтернативой может быть преобразование вашего числа в его двоичное представление с помощью Convert.ToString () (с указанием базы 2 для двоичного кода). Затем просто пройдитесь по строке и для каждой встреченной «1» вычислите эквивалентную мощность основания 2 на основе текущей позиции. Этот подход не требует жестко запрограммированного массива для степеней 2:

Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
    Dim values() As Integer = {64, 80, 162}
    For Each value As Integer In values
        Dim powers As List(Of Integer) = GetBinaryPowers(value)
        Debug.Print(value & ": " & String.Join(", ", powers))
    Next
End Sub

Private Function GetBinaryPowers(ByVal number As Integer) As List(Of Integer)
    Dim powers As New List(Of Integer)
    Dim strBinary As String = Convert.ToString(number, 2)
    For i As Integer = 0 To strBinary.Length - 1
        If strBinary(i) = "1" Then
            powers.Add(Math.Pow(2, strBinary.Length - (i + 1)))
        End If
    Next
    Return powers
End Function

Выход:

64: 64
80: 64, 16
162: 128, 32, 2

Answer 2

Dim number As Int64 = 162
Dim factor As Integer = 0
Dim power As Int64
Dim numbers As New List(Of Int64)
Do
    power = 2 ^ factor
    If power > number Then
        Exit Do
    End If

    If (number And power) = power Then
        numbers.Add(power)
    End If

    factor += 1
Loop

Answer 3

Вы можете использовать следующую функцию, чтобы получить Integer массив со всеми числами последовательности:

'function
Private Function GetNumbers(ByVal sumValue As Integer) As Integer()
    Dim seqNumbers As Integer() = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536}
    Dim seqNumbersInSum As New ArrayList

    'run through all numbers of the sequence.
    For seqIndex As Integer = UBound(seqNumbers) To 0 Step -1

        'don't use numbers of the sequence larger than the current sum value.
        If seqNumbers(seqIndex) > sumValue Then
            Continue For
        End If

        'subtract the current sequence number from sum value. Also add the used sequence number to the array list of used sequence numbers.
        sumValue -= seqNumbers(seqIndex)
        seqNumbersInSum.Add(seqNumbers(seqIndex))

        'in case the sum the result is 0 all sequence numbers are found.
        If sumValue = 0 Then
            Exit For
        End If
    Next

    'return the used sequence numbers.
    Return seqNumbersInSum.ToArray(GetType(Integer))
End Function

'usage
GetNumbers(162) ' {128, 32, 2}
GetNumbers(80)  ' {64, 16}
GetNumbers(64)  ' {64}