Find smaller difference between a number and a list

[rony2006]

Hi,

I try to develop a software and I need a algorithm that will return me the smallest difference  between a number (X) and a list of number (array):

https://i.imgur.com/dOevZQr.png

In my example, if I make a sum between number G and number M I will get smallest difference to the number X (3,591,226.64).

 

I want to input a array with numbers and to give the value of X. The script should give me the most closer combination of number to the value of x. 

From the array I can use 1, 2 or multiple values to make the sum to be compared with X.

The difference can be both positive or negative, the idea is to be much closer to X value.

 

Any help will be appreciated (I am willing to pay also for this).

 

Regards,

[rony2006]

I found this code by @Melba23 but it looks only for combinations that will give the exact number not the closest:

 

#include <Array.au3>

$iRequiredSum = 12

Global $aArray = [7, 8, 5, 3, 2, 1, 4, 6]

; Increase the number of factors on each pass
For $iSet = 1 To UBound($aArray)
    ; Determine the possible combinations
    $aCombinations = _ArrayCombinations($aArray, $iSet, "+")
    ; For each combination
    For $j = 1 To $aCombinations[0]
        ; Break into factors
        $aFactors = StringSplit($aCombinations[$j], "+")
        ; Sum factors
        $iSum = 0
        For $k = 1 To $aFactors[0]
            $iSum += $aFactors[$k]
        Next
        ; If sum is required value
        If $iSum = $iRequiredSum Then
            ; Write caombination
            ConsoleWrite($aCombinations[$j] & " = " & $iRequiredSum & @CRLF)
        EndIf
    Next
Next

 

Any idea how i can adjust that to give me the most closest values to $iRequiredSum

[jchd]

This is one of the myriad of variants of the knapsack problem (KP), known to be NP-complete in many variants and polynomial at best. So don't expect a magical algorithm. I'd call your problem "approximate subset sum". See for instance https://en.wikipedia.org/wiki/Subset_sum_problem

The code posted above is pure brute force and can be somehow made faster as well as modified to approximate the target value.
The array of values can be pruned to remove entries which are larger than the target + the smallest value. That will limit the number of combinations to check.
If we don't precompute all remaining combinations, we can limit search with similar bounds, provided entries are first sorted.

There are a large number of algorihms you can use. Dynamic programming is often cited, among more ad-hoc approaches.

[rony2006]

expandcollapse popup

#include <Array.au3>

$iRequiredSum = 3591226

Global $aArray = [1378908,1634314,15713665,1149042,1797187,18754341,1429697,1509035,13257814,1811223,1508925,13817384,2100215,1540744,12836514,1616225,1444406,12190430,1653099,620083,4901735]
Global $Valori[1][3]


; Increase the number of factors on each pass
For $iSet = 1 To UBound($aArray)
; Determine the possible combinations
$aCombinations = _ArrayCombinations($aArray, $iSet, "+")
; For each combination
For $j = 1 To $aCombinations[0]
; Break into factors
$aFactors = StringSplit($aCombinations[$j], "+")
; Sum factors
$iSum = 0
For $k = 1 To $aFactors[0]
$iSum += $aFactors[$k]
Next

ConsoleWrite($j & @crlf)

if abs($iRequiredSum - $iSum) < $iRequiredSum / 4 Then

_ArrayAdd($Valori, $aCombinations[$j] & "=" &$iSum    & "=" &  abs($iRequiredSum - $iSum), 0,"=")

endif
; If sum is required value

Next
Next

;_ArraySort($Valori, 0, 0, 0, 2)

;_arraydisplay($Valori)


exit

#include <Excel.au3>
#include <MsgBoxConstants.au3>

; Create application object and create a new workbook
Local $oExcel = _Excel_Open()
If @error Then Exit MsgBox($MB_SYSTEMMODAL, "Excel UDF: _Excel_RangeWrite Example", "Error creating the Excel application object." & @CRLF & "@error = " & @error & ", @extended = " & @extended)
Local $oWorkbook = _Excel_BookNew($oExcel)
If @error Then
    MsgBox($MB_SYSTEMMODAL, "Excel UDF: _Excel_RangeWrite Example", "Error creating the new workbook." & @CRLF & "@error = " & @error & ", @extended = " & @extended)
    _Excel_Close($oExcel)
    Exit
EndIf

; Write a part of a 2D array to the active sheet in the active workbook
;Local $aArray2D[3][5] = [[11, 12, 13, 14, 15], [21, 22, 23, 24, 25], [31, 32, 33, 34, 35]]
_Excel_RangeWrite($oWorkbook, $oWorkbook.Activesheet, $Valori, "B1")
If @error Then Exit MsgBox($MB_SYSTEMMODAL, "Excel UDF: _Excel_RangeWrite Example 3", "Error writing to worksheet." & @CRLF & "@error = " & @error & ", @extended = " & @extended)
MsgBox($MB_SYSTEMMODAL, "Excel UDF: _Excel_RangeWrite Example 3", "2D array successfully written.")

I adjusted the code to fit my needs but I noticed 2 problems:

If I store the resulted sum in a array and then I sort that array to get the smallest different then sorting is not correct.

Another things is that is taking a lot of time to calculate. I added there a condition that the array should be filled only if the difference is smaller then 25% of the required sum but still didnt improved a lot the speed.

 

Current code finished filling the array in >Exit code: 0    Time: 479.3

Any ideas?

Edited September 29, 2018 by rony2006

[RTFC]

A similar problem was discussed in this thread.

[Malkey]

This example only sums up to any 3 numbers to find the minimum absolute difference from the given number "X".

expandcollapse popup

Local $aNums = [["Number", "Value"], _
        ["A", "1,378,908.00"], _
        ["B", "1,634,313.90"], _
        ["C", "15,713,665.11"], _
        ["D", "1,149,041.80"], _
        ["E", "1,797,187.20"], _
        ["F", "18,754,341.27"], _
        ["G", "1,429,697.20"], _
        ["H", "1,509,035.10"], _
        ["I", "13,257,813.79"], _
        ["J", "1,811,222.75"], _
        ["K", "1,508,924.70"], _
        ["L", "13,817,383.94"], _
        ["M", "2,100,214.65"], _
        ["N", "1,540,743.60"], _
        ["O", "12,836,514.49"], _
        ["P", "1,616,224.64"]]
Local $sX = "3,591,226.64"
Local $iX = Number(StringReplace($sX, ",", ""))
;Local $iCount = 0 ; For testing purposes only.

; Make 2nd column of $aNums array all numbers
For $i = 1 To UBound($aNums) - 1
    $aNums[$i][1] = Number(StringReplace($aNums[$i][1], ",", ""))
Next

; An array with the smallest difference ($iX - sum of up to 3 numbers from 2nd column of $aNums array.)
Local $aMinDiff[2] = ["Abs(X - " & $aNums[1][0] & ")", Abs($iX - $aNums[1][1])] ; Initialize $aMinDiff array.

; Find the minimum difference
For $i = 1 To UBound($aNums) - 1
    If Abs($iX - $aNums[$i][1]) < $aMinDiff[1] Then ; Where the minimum difference is (X - any 1 element in array)
        $aMinDiff[0] = "Abs(X - " & $aNums[$i][0] & ")"
        $aMinDiff[1] = Abs($iX - $aNums[$i][1])
    EndIf

    For $j = $i + 1 To UBound($aNums) - 1 ; Where the minimum difference is (X - the sum of any 2 elements in array)
        If Abs($aNums[$i][1] + $aNums[$j][1] - $iX) < $aMinDiff[1] Then
            $aMinDiff[0] = "Abs(X - (" & $aNums[$i][0] & "  + " & $aNums[$j][0] & "))"
            $aMinDiff[1] = Abs($iX - ($aNums[$i][1] + $aNums[$j][1]))
        EndIf

        For $k = $j + 1 To UBound($aNums) - 1 ; Where the minimum difference is (X - the sum of any 3 elements in array)
            If Abs($aNums[$i][1] + $aNums[$j][1] + $aNums[$k][1] - $iX) < $aMinDiff[1] Then
                $aMinDiff[0] = "Abs(X - (" & $aNums[$i][0] & "  + " & $aNums[$j][0] & "  + " & $aNums[$k][0] & "))"
                $aMinDiff[1] = Abs($iX - ($aNums[$i][1] + $aNums[$j][1] + $aNums[$k][1]))
            EndIf
            ;$iCount += 1 ; For testing purposes only.
            ;ConsoleWrite($iCount & "  " & $i & "  " & $j & "  " & $k & @CRLF) ; For testing purposes only.
        Next
    Next
Next

MsgBox(0, "Results", $aMinDiff[0] & " = " & StringRegExpReplace(Round($aMinDiff[1], 2), '(\d+?)(?=(\d{3})+\.)', '$1,'))

; Returns: Abs(X - (E  + J)) = 17,183.31