Добавление значений в различных комбинациях

Question

Не знаю, как лучше это объяснить, кроме как на примере ...

Представьте себе, что у клиента есть 10 неоплаченных счетов, и однажды они предоставят вам чек, но не сообщат, для каких счетов он предназначен.

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

---

Мое нынешнее мышление - это своего рода метод грубой силы, который включает использование функции самовызова, которая выполняет все возможности ( см. Текущую версию ).

Например, с 3 числами есть 15 способов сложить их вместе:

1. A
2. A + B
3. A + B + C
4. A + C
5. A + C + B
6. B
7. B + A
8. B + A + C
9. B + C
10. B + C + A
11. C
12. C + A
13. C + A + B
14. C + B
15. C + B + A

Что, если вы удалите дубликаты, даст вам 7 уникальных способов сложить их вместе:

1. A
2. A + B
3. A + B + C
4. A + C
5. B
6. B + C
7. C

Тем не менее, этот вид разваливается после того, как у вас есть:

• 15 чисел (32 767 возможностей / ~ 2 секунды для расчета)
• 16 чисел (65 535 возможностей / ~ 6 секунд для расчета)
• 17 чисел (131 071 возможностей / ~ 9 секунд для расчета)
• 18 чисел (262 143 возможности / ~ 20 секунд для расчета)

Где бы я хотел, чтобы эта функция обрабатывала не менее 100 чисел.

Итак, есть идеи, как это улучшить? (на любом языке)

Answer 1

Это строго для количества возможностей и не учитывает перекрытия. Я не уверен, что вы хотите.

Рассмотрим состояния, в которых одно значение может быть одновременно - оно может быть либо включено, либо исключено. Это два разных состояния, поэтому количество разных состояний для всех n элементов будет 2 ^ n. Однако есть одно государство, которое не требуется; это состояние, когда ни одно из чисел не включено.

И, таким образом, для любых n чисел число комбинаций равно 2 ^ n-1.

def setNumbers(n): return 2**n-1

print(setNumbers(15))

Эти выводы очень тесно связаны с комбинациями и перестановками.

---

Вместо этого, однако, я думаю, что вы, возможно, скажете, что при заданном наборе значений любая комбинация их суммирует значение k. Для этого Билла Ящерица указал вам правильное направление.

Исходя из этого и учитывая, что я не прочитал всю статью в Википедии, я предлагаю этот алгоритм на Python:

def combs(arr):
    r = set()

    for i in range(len(arr)):
        v = arr[i]
        new = set()

        new.add(v)
        for a in r: new.add(a+v)
        r |= new

    return r


def subsetSum(arr, val):
    middle = len(arr)//2

    seta = combs(arr[:middle])
    setb = combs(arr[middle:])

    for a in seta:
        if (val-a) in setb:
            return True

    return False

print(subsetSum([2, 3, 5, 8, 9], 8))

В основном алгоритм работает так:

1. Разбивает список на 2 списка примерно на половину длины. [О (п)]
2. Находит набор подмножеств сумм. [O (2 ^{n / 2} n)]
3. Прокручивает первый набор до 2 ^{floor (n / 2)} -1 значений, видя, будет ли другое значение во втором наборе достигать k. [O (2 ^{n / 2} n)]

Так что я думаю, что в целом он работает в O (2 ^{n / 2} n) - все еще довольно медленно, но намного лучше.

Answer 2

Это довольно распространенный вариант проблемы суммы подмножеств , и это действительно довольно сложно. Раздел о решении для динамического программирования с псевдополиномиальным временем на странице, на которую вы ссылаетесь, - вот что вам нужно.

Answer 3

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

Это больше похоже на проблему внесения изменений, в которой есть куча статей, в которых подробно описывается, как ее решить. Google указал мне здесь: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.3243

Answer 4

Это вариант с похожей проблемой.

Но вы можете решить эту проблему, создав счетчик с n битами. Где n - количество чисел. Затем вы считаете от 000 до 111 (n 1) и для каждого числа 1 эквивалентно доступному числу:

001 = A
010 = B
011 = A+B
100 = C
101 = A+C
110 = B+C
111 = A+B+C

(Но это был не вопрос, ну, я оставляю это как цель).

Answer 5

Похоже на проблему упаковки бункера . Они являются NP-полными, то есть практически невозможно найти идеальное решение для больших наборов задач. Но вы можете довольно близко подойти к эвристике, которая, вероятно, применима к вашей проблеме, даже если это не совсем проблема упаковки бина.

Answer 6

Для справки, вот довольно простой Java-код, который использует рекурсию для решения этой проблемы. Он оптимизирован для простоты, а не производительности, хотя при 100 элементах он кажется довольно быстрым. С 1000 элементов это занимает значительно больше времени, поэтому, если вы обрабатываете большие объемы данных, вам лучше использовать более сложный алгоритм.

public static List<Double> getMatchingAmounts(Double goal, List<Double> amounts) {
    List<Double> remaining = new ArrayList<Double>(amounts);

    for (final Double amount : amounts) {
        if (amount > goal) {
            continue;
        } else if (amount.equals(goal)) {
            return new ArrayList<Double>(){{ add(amount); }};
        }

        remaining.remove(amount);

        List<Double> matchingAmounts = getMatchingAmounts(goal - amount, remaining);
        if (matchingAmounts != null) {
            matchingAmounts.add(amount);
            return matchingAmounts;
        }
    }

    return null;
}

Answer 7

Вот оптимизированная объектно-ориентированная версия точного целочисленного решения задачи о подмножествах (Horowitz, Sahni, 1974). На моем ноутбуке (в этом нет ничего особенного) этот класс vb.net решает 1900 подмножеств в секунду (для 20 наименований):

Option Explicit On

Public Class SubsetSum
    'Class to solve exact integer Subset Sum problems'
    ''
    ' 06-sep-09 RBarryYoung Created.'
    Dim Power2() As Integer = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32764}
    Public ForceMatch As Boolean
    Public watch As New Stopwatch
    Public w0 As Integer, w1 As Integer, w1a As Integer, w2 As Integer, w3 As Integer, w4 As Integer


    Public Function SolveMany(ByVal ItemCount As Integer, ByVal Range As Integer, ByVal Iterations As Integer) As Integer
        ' Solve many subset sum problems in sequence.'
        ''
        ' 06-sep-09 RBarryYoung Created.'
        Dim TotalFound As Integer
        Dim Items() As Integer
        ReDim Items(ItemCount - 1)

        'First create our list of selectable items:'
        Randomize()
        For item As Integer = 0 To Items.GetUpperBound(0)
            Items(item) = Rnd() * Range
        Next

        For iteration As Integer = 1 To Iterations
            Dim TargetSum As Integer
            If ForceMatch Then
                'Use a random value but make sure that it can be matched:'

                ' First, make a random bitmask to use:'
                Dim bits As Integer = Rnd() * (2 ^ (Items.GetUpperBound(0) + 1) - 1)

                ' Now enumerate the bits and match them to the Items:'
                Dim sum As Integer = 0
                For b As Integer = 0 To Items.GetUpperBound(0)
                    'build the sum from the corresponding items:'
                    If b < 16 Then
                        If Power2(b) = (bits And Power2(b)) Then
                            sum = sum + Items(b)
                        End If
                    Else
                        If Power2(b - 15) * Power2(15) = (bits And (Power2(b - 15) * Power2(15))) Then
                            sum = sum + Items(b)
                        End If
                    End If
                Next
                TargetSum = sum

            Else
                'Use a completely random Target Sum (low chance of matching): (Range / 2^ItemCount)'
                TargetSum = ((Rnd() * Range / 4) + Range * (3.0 / 8.0)) * ItemCount
            End If

            'Now see if there is a match'
            If SolveOne(TargetSum, ItemCount, Range, Items) Then TotalFound += 1
        Next

        Return TotalFound
    End Function

    Public Function SolveOne(ByVal TargetSum As Integer, ByVal ItemCount As Integer _
                            , ByVal Range As Integer, ByRef Items() As Integer) As Boolean
        ' Solve a single Subset Sum problem:  determine if the TargetSum can be made from'
        'the integer items.'

        'first split the items into two half-lists: [O(n)]'
        Dim H1() As Integer, H2() As Integer
        Dim hu1 As Integer, hu2 As Integer
        If ItemCount Mod 2 = 0 Then
            'even is easy:'
            hu1 = (ItemCount / 2) - 1 : hu2 = (ItemCount / 2) - 1
            ReDim H1((ItemCount / 2) - 1), H2((ItemCount / 2) - 1)
        Else
            'odd is a little harder, give the first half the extra item:'
            hu1 = ((ItemCount + 1) / 2) - 1 : hu2 = ((ItemCount - 1) / 2) - 1
            ReDim H1(hu1), H2(hu2)
        End If

        For i As Integer = 0 To ItemCount - 1 Step 2
            H1(i / 2) = Items(i)
            'make sure that H2 doesnt run over on the last item of an odd-numbered list:'
            If (i + 1) <= ItemCount - 1 Then
                H2(i / 2) = Items(i + 1)
            End If
        Next

        'Now generate all of the sums for each half-list:   [O( 2^(n/2) * n )]  **(this is the slowest step)'
        Dim S1() As Integer, S2() As Integer
        Dim sum1 As Integer, sum2 As Integer
        Dim su1 As Integer = 2 ^ (hu1 + 1) - 1, su2 As Integer = 2 ^ (hu2 + 1) - 1
        ReDim S1(su1), S2(su2)

        For i As Integer = 0 To su1
            ' Use the binary bitmask of our enumerator(i) to select items to use in our candidate sums:'
            sum1 = 0 : sum2 = 0
            For b As Integer = 0 To hu1
                If 0 < (i And Power2(b)) Then
                    sum1 += H1(b)
                    If i <= su2 Then sum2 += H2(b)
                End If
            Next
            S1(i) = sum1
            If i <= su2 Then S2(i) = sum2
        Next

        'Sort both lists:   [O( 2^(n/2) * n )]  **(this is the 2nd slowest step)'
        Array.Sort(S1)
        Array.Sort(S2)

        ' Start the first half-sums from lowest to highest,'
        'and the second half sums from highest to lowest.'
        Dim i1 As Integer = 0, i2 As Integer = su2

        ' Now do a merge-match on the lists (but reversing S2) and looking to '
        'match their sum to the target sum:     [O( 2^(n/2) )]'
        Dim sum As Integer
        Do While i1 <= su1 And i2 >= 0
            sum = S1(i1) + S2(i2)
            If sum < TargetSum Then
                'if the Sum is too low, then we need to increase the ascending side (S1):'
                i1 += 1
            ElseIf sum > TargetSum Then
                'if the Sum is too high, then we need to decrease the descending side (S2):'
                i2 -= 1
            Else
                'Sums match:'
                Return True
            End If
        Loop

        'if we got here, then there are no matches to the TargetSum'
        Return False
    End Function

End Class

Вот код Forms, который будет сопровождать его:

Public Class frmSubsetSum

    Dim ssm As New SubsetSum

    Private Sub btnGo_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnGo.Click
        Dim Total As Integer
        Dim datStart As Date, datEnd As Date
        Dim Iterations As Integer, Range As Integer, NumberCount As Integer

        Iterations = CInt(txtIterations.Text)
        Range = CInt(txtRange.Text)
        NumberCount = CInt(txtNumberCount.Text)

        ssm.ForceMatch = chkForceMatch.Checked

        datStart = Now

        Total = ssm.SolveMany(NumberCount, Range, Iterations)

        datEnd = Now()

        lblStart.Text = datStart.TimeOfDay.ToString
        lblEnd.Text = datEnd.TimeOfDay.ToString
        lblRate.Text = Format(Iterations / (datEnd - datStart).TotalMilliseconds * 1000, "####0.0")

        ListBox1.Items.Insert(0, "Found " & Total.ToString & " Matches out of " & Iterations.ToString & " tries.")
        ListBox1.Items.Insert(1, "Tics 0:" & ssm.w0 _
                                & " 1:" & Format(ssm.w1 - ssm.w0, "###,###,##0") _
                                & " 1a:" & Format(ssm.w1a - ssm.w1, "###,###,##0") _
                                & " 2:" & Format(ssm.w2 - ssm.w1a, "###,###,##0") _
                                & " 3:" & Format(ssm.w3 - ssm.w2, "###,###,##0") _
                                & " 4:" & Format(ssm.w4 - ssm.w3, "###,###,##0") _
                                & ", tics/sec = " & Stopwatch.Frequency)
    End Sub
End Class

Дайте мне знать, если у вас есть какие-либо вопросы.

Answer 8

Я не знаю, как часто это будет работать на практике, поскольку существует много исключений из этого упрощенного случая, но вот мысль:

В идеальном мире счета будут оплачены до определенного момента. Люди будут платить A, или A + B, или A + B + C, но не A + C - если они получили счет C, то они уже получили счет B. В идеальном мире проблема не в том, чтобы найти комбинацию, а в том, чтобы найти точку вдоль линии.

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

Вернувшись в реальный мир, это тривиально быстрая проверка, которую вы можете сделать перед тем, как приступить к тяжелому сокращению чисел или преследовать их. Любые удары, которые он получает, являются бонусом:)