Android Question Algorithm to find Sum of numbers?

[syncmaster13]

Hi

I’m trying to find an example of an algorithm that will find an optimal set of numbers from a fixed list, which sum will be the closest to a given number. Example:


List of fixed Numbers: “0.147, 0.148, 0.149, 0.05, 0.1, 0.15, 0.2, 0.25, 0.3, 0.35, 0.4, 0.45, 0.5, 0.55, 0.6, 0.65, 0.7, 0.75, 0.8, 0.85, 0.9, 0.95, 1” and given number is : 1.997” The answer should be :1 + 0.8 + 0.05 + 0.147.


Thanks

 

[Beja]

start with the lowest number, then if equal or greater than the seed number then exit this reply.
if smaller, add to it the smallest from the reminder of the number (excluding the one (or ones) you picked)
each iteration do comparison between the new sum and the seed number until you arrive at the right sum.
Then list the numbers in a new set.. you should have saved the added numbers in an array beside adding them up.

my two cents.

 

[syncmaster13]

Thanks for the response

I was also hoping to see a working example in basic4android, since I’m just a beginner I never used arrays.

Thanks

 

[Eric H]

building on Beja's response, here is what I would do:

- Use a FOR loop to read the values into a list using the List's ADD function
- Sort the values using the List's SORT function
- Now that you have a List (similar to an array) of numbers in order...
- Use another loop to iterate through each number in your formula, and get the difference.
- Stop when the difference is getting larger

Here is some information to get you started with Lists. See how far you can get (even pseudo-code) with that, and ask for more help if you get stuck.
http://www.b4x.com/android/help/collections.html#list

 

[Erel]

Here is a "brute force" solution. Note that it finds a set of numbers that sums to the closest number. There might be a another smaller set with the same sum. It shouldn't be difficult to modify it to find the smallest set.

Sub Activity_Create(FirstTime As Boolean)
   Log(FindClosetSum(Array As Float(0.147, 0.148, 0.149, 0.05, 0.1, 0.15, 0.2, 0.25, 0.3, 0.35, 0.4, 0.45, 0.5, 0.55, 0.6, 0.65, 0.7, 0.75, 0.8, 0.85, 0.9, 0.95, 1), _
     1.997))
   Log(FindClosetSum(Array As Float(1, 2, 3, 4), 5.6))
End Sub

Sub FindClosetSum(Nums() As Float, Target As Float) As List
   Dim minDistance = 3.4028235E38 As Float 'max value
   Dim minI As Int = 0
   For i = 1 To Bit.ShiftLeft(1, Nums.Length) - 1
     Dim sum As Float = 0
     For n = 0 To Nums.Length - 1
       If Bit.AND(Bit.ShiftLeft(1, n), i) <> 0 Then
         If sum > Target Then Exit
         sum = sum + Nums(n)
       End If
     Next
     If Abs(sum - Target) < minDistance Then
       minDistance = Abs(sum - Target)
       minI = i
       If minDistance = 0 Then Exit
     End If
   Next
   Log("Distance: " & minDistance)
   Dim l1 As List
   l1.Initialize
   For n = 0 To Nums.Length - 1
     If Bit.AND(Bit.ShiftLeft(1, n), minI) <> 0 Then
       l1.Add(Nums(n))
     End If
   Next
   Return l1
End Sub

Make sure to run it in Release mode.

 

[syncmaster13]

Thanks

I assume he difference between debug mode and release is only speed. I quickly run the code and distance shows 0.400 . Should I see set of numbers instead. ?

 

[Erel]

I assume he difference between debug mode and release is only speed.

This is correct.

You should also see the content of the list which holds the numbers.