给定大量数字且不重叠，如何找到总和为特定 X Y 和 Z 的 3 个数字组合？

Question

我有大约 1000 个号码的列表

我需要将其分成 3 个不重叠的组，等于特定的总和

有什么建议最好使用 Excel 论坛或 VBA 吗？

我尝试在 Excel 中使用 If() 和 Subtotal()，但当剩余数字不适合任何现有小计时，在列表末尾出现“假”错误

查看具有较小数组的示例公式（我可以使用猜测和检查轻松查看 Excel 是否正确）

    =IF(SUMIFS($A$6:A7, D$6:D7, $D$5) + A8 <= 1810, 100,
        IF(SUMIFS($A$6:A7, D$6:D7, $E$5) + A8 <= 850, 200,
            IF(SUMIFS($A$6:A7, D$6:D7, $F$5) + A8 <= 800, 300, "")
        )
    )

我尝试在 Excel 宏中运行递归脚本

Do Until Range("O4") = True
    Range("O4").Select
    Selection.Copy
    Range("O3").Select
    Selection.PasteSpecial Paste:=xlPasteValues, Operation:=xlNone, SkipBlanks:=False, Transpose:=False
Loop


It only worked on lists of 10 numbers or so; it reached the limit when using longer lists, how can I get it working for longer lists as well?

Thanks

Answer 1

我不认为 VBA 是最好的选择。 你可以在 Excel 中运行 Python，我认为在这种情况下它会成为一个更好的工具。 不管怎样，这是我几年前为一个非常相似的问题编写的非常笨重的代码。 它在小型数据集上运行得很好，但我不知道它在 1000 个数字输入上运行多长时间。

    Sub DivideIntoThreeGroups()
        Dim numbers As Variant
        Dim target1 As Double, target2 As Double, target3 As Double
        Dim group1Sum As Double, group2Sum As Double, group3Sum As Double
        Dim i As Long
        Dim assignments() As Integer
        Dim maxIterations As Long
        Dim changeMade As Boolean
        
        ' Load the numbers into an array
        numbers = Range("A1:A10").Value
    
        ' Define your target sums
        target1 = 3 ' Replace with your specific target for group 1
        target2 = 18 ' Replace with your specific target for group 2
        target3 = 8 ' Replace with your specific target for group 3
    
        ' Initialize group sums
        group1Sum = 0
        group2Sum = 0
        group3Sum = 0
    
        ' Initialize the assignment array (1 = group 1, 2 = group 2, 3 = group 3)
        ReDim assignments(LBound(numbers) To UBound(numbers))
        
        ' Assign numbers randomly to the three groups
        Randomize
        For i = LBound(numbers) To UBound(numbers)
            assignments(i) = Int(3 * Rnd) + 1
            If assignments(i) = 1 Then
                group1Sum = group1Sum + numbers(i, 1)
            ElseIf assignments(i) = 2 Then
                group2Sum = group2Sum + numbers(i, 1)
            Else
                group3Sum = group3Sum + numbers(i, 1)
            End If
        Next i
    
        ' Max number of iterations to adjust the group assignments
        maxIterations = 10000
        changeMade = True
        
        ' Adjust groups iteratively to reach the target sums
        While changeMade And maxIterations > 0
            changeMade = False
            For i = LBound(numbers) To UBound(numbers)
                ' Check if group assignments need adjusting
                If assignments(i) = 1 And group1Sum > target1 Then
                    ' Try moving to group 2 or group 3
                    If group2Sum + numbers(i, 1) <= target2 Then
                        assignments(i) = 2
                        group1Sum = group1Sum - numbers(i, 1)
                        group2Sum = group2Sum + numbers(i, 1)
                        changeMade = True
                    ElseIf group3Sum + numbers(i, 1) <= target3 Then
                        assignments(i) = 3
                        group1Sum = group1Sum - numbers(i, 1)
                        group3Sum = group3Sum + numbers(i, 1)
                        changeMade = True
                    End If
                ElseIf assignments(i) = 2 And group2Sum > target2 Then
                    ' Try moving to group 1 or group 3
                    If group1Sum + numbers(i, 1) <= target1 Then
                        assignments(i) = 1
                        group2Sum = group2Sum - numbers(i, 1)
                        group1Sum = group1Sum + numbers(i, 1)
                        changeMade = True
                    ElseIf group3Sum + numbers(i, 1) <= target3 Then
                        assignments(i) = 3
                        group2Sum = group2Sum - numbers(i, 1)
                        group3Sum = group3Sum + numbers(i, 1)
                        changeMade = True
                    End If
                ElseIf assignments(i) = 3 And group3Sum > target3 Then
                    ' Try moving to group 1 or group 2
                    If group1Sum + numbers(i, 1) <= target1 Then
                        assignments(i) = 1
                        group3Sum = group3Sum - numbers(i, 1)
                        group1Sum = group1Sum + numbers(i, 1)
                        changeMade = True
                    ElseIf group2Sum + numbers(i, 1) <= target2 Then
                        assignments(i) = 2
                        group3Sum = group3Sum - numbers(i, 1)
                        group2Sum = group2Sum + numbers(i, 1)
                        changeMade = True
                    End If
                End If
            Next i
            maxIterations = maxIterations - 1
        Wend
    
        ' Output the result to columns B, C, and D
        For i = LBound(numbers) To UBound(numbers)
            If assignments(i) = 1 Then
                Range("B" & i).Value = numbers(i, 1) ' Group 1
            ElseIf assignments(i) = 2 Then
                Range("C" & i).Value = numbers(i, 1) ' Group 2
            Else
                Range("D" & i).Value = numbers(i, 1) ' Group 3
            End If
        Next i
    
        ' Final output for verification
        MsgBox "Group 1 sum: " & group1Sum & vbCrLf & "Group 2 sum: " & group2Sum & vbCrLf & "Group 3 sum: " & group3Sum
    
    End Sub