Algorithm for Adding/Subtracting numbers to find if number can be made

[ur]

I was wondering if there is an efficient premade algorithm for determining if the sum/difference of a group of numbers can equal a different number. Example:

5, 8, 10, 2, using + or -, to equal 9. 5 - 8 = -3 + 10 = 7 + 2 = 9

It is somewhere nearer to Knapsack problem.

Thanks in Advance.

[SadBunny]

The sum/diff of any two numbers in the group, or the sum/diff of any number of numbers in the group? Are all numbers in the group unique? Can there be negative numbers? Is there a known boundary to the numbers? Is the special number guaranteed to be between the highest and the lowest number in the group?

[ur]

expandcollapse popup

Example data:
 
151.15   --> is the number we need ti get by doing arithmetic operations(only add or subtract) on below set of numbers (each number can be used any number of times).


 
 


 

 
 
Set of numbers:

2.77

8.24

2.77

3.48

3.48

3.99

3.48

3.48

3.48

17.4

3.48

3.48

3.48

2.77

4.85

5.67

17.67

2.77

3.48

2.77

3.58

2.77

3.48

2.77

2.77

3.48

3.48

2.77

3.48

3.48

3.48

3.48

3.48

2.77

2.77

3.48

3.48

2.77

3.48

3.48

3.48

3.48

4.8

5

6.76

3.48

3.48

3.48

14.4

17.94

4.85

3.48

3.48

3.48

3.48

8.39

4.58

4.85

3.48

2.77

3.48

2.77

2.77

3.48

3.48

3.48

4.03

3.48

2.77

21.76

3.48

3.48

10.03

3.48

2.77

9.21

2.77

3.65

1.23

1.23

1.11

0.37

0.47

0.47

0.54

0.47

0.47

0.47

2.34

0.47

0.47

0.47

0.37

0.65

0.76

2.37

0.37

0.47

0.37

0.48

1.23

1.33

1.23

0.37

0.47

0.47

0.37

0.47

0.47

1.33

1.33

0.47

0.37

0.37

0.47

0.47

0.37

0.47

0.47

0.47

0.47

0.64

0.67

0.91

0.47

0.47

0.47

1.94

2.41

1.51

1.33

0.47

0.47

0.47

1.13

1.48

0.65

0.47

0.37

0.47

0.37

0.37

1.33

0.47

0.47

0.54

0.47

0.37

2.92

0.47

0.47

1.35

0.47

0.37

1.24

0.37

0.46

 

Edited July 16, 2015 by Melba23
Added tags

[jchd]

There's nothing "premade" you're going to find here. In all case, scale up all values (including target) to integers to avoid floating-point issues (here, * 100), then feed the baby to a classical knapsack variant. Of course you know it's NP-Complete.

[UEZ]

This is what I did meanwhile for your initial post:

;Brute force method

Global $aIntegers[4] = [5, 8, 10, 2]
ConsoleWrite(BruteForce_Calc($aIntegers, 1) & "=" & 1 & @CRLF)
ConsoleWrite(BruteForce_Calc($aIntegers, 9) & "=" & 9 & @CRLF)
ConsoleWrite(BruteForce_Calc($aIntegers, 15) & "=" & 15 & @CRLF)
ConsoleWrite(BruteForce_Calc($aIntegers, -11) & "=" & -11 & @CRLF)


Func BruteForce_Calc(ByRef $aIntegers, $iTarget)
    Local $aOp[2] = ["+", "-"], $i = 1, $j, $z = UBound($aIntegers), $iCalc, $k, $l, $sTerm
    Do
        For $j = 0 To UBound($aIntegers) - 1
            $l = 2^($z - $j)
            $k = (Mod(Mod($i - 1, $l), $i)) < ($l / 2) ? 0 : 1
            $sTerm &= $aOp[$k] & $aIntegers[$j]
        Next
        $iCalc = Execute($sTerm)
        If $iCalc = $iTarget Then Return (StringLeft($sTerm, 1) = "+" ? StringTrimLeft($sTerm, 1) : $sTerm)
        $sTerm = ""
        $i += 1
    Until $i > 2 ^ $z
EndFunc

I didn't test it properly and thus I don't know whether it will work also for other variations.

 

Something similar: https://www.autoitscript.com/forum/topic/139260-autoit-snippets/?do=findComment&comment=1058220

Edited July 16, 2015 by UEZ