CODEWITHSUNDEEP
algorithmnumberssum
Whencesoever
Whencesoever

Reputation: 2306

Algorithm to take the best set of numbers to sum

I am trying to find algorithm to sum small amounts of money from table/list to be equal or possibly the closest(but not larger) than ceratin number.

Let me explain it by example. I've got a list with numbers :
{ 1.23 ; 3.45 ; 20.11 ; 100.13 ; 200.08 }

and the number i am trying to get is 123.69

So it should take { 3.45 ; 20.11 ; 100.13 } = 123.69

If the number is 122 it should not take the same, but { 20.11 ; 100.13 ; 1.23 } = 121.47

Is there any idea how to write something like that?

Upvotes: 4

Views: 3066

Answers (2)

Whencesoever
Whencesoever

Reputation: 2306

I wrote the following code that works perfectly in VB.NET, but has problem in VBA. Can you try to help me find a mistake?

Dim L() As Integer
bestAll = 0

K = 35.3903

ReDim list(0 To 17) As Integer
ReDim L(0 To 17) As Integer
Dim W As Integer
Dim bool As Boolean

   Dim B(16) As Double
   B(0) = 0.042
   B(1) = 0.1286
   B(2) = 0.1472
   B(3) = 0.1534
   B(4) = 0.2008
   B(5) = 1.4679
   B(6) = 1.5954
   B(7) = 2.6748
   B(8) = 12.1078
   B(9) = 12.1272
   B(10) = 12.4154
   B(11) = 12.4978
   B(12) = 15.4142
   B(13) = 28.3464
   B(14) = 34.8652
   B(15) = 38.1519
   B(16) = 42.8154
For W = 0 To 16
           bool = Proc(0, W, L, 0, B)
        Next W

and here Function Proc:

Public Function Proc(best As Double, I As Integer, L() As Integer, count As Integer, A() As Double) As Boolean
        Dim newbest As Double
        newbest = 0
        If ((best + A(I)) <= K) Then
            newbest = best + A(I)
            L(count) = I
            count = count + 1
            If (newbest > bestAll) Then
                bestAll = newbest
                listcount = count
                Dim j1 As Integer
                For j1 = 0 To count - 1
                    list(j1) = L(j1)
                Next j1
            End If
        Else
            Proc = False
        End If
        Dim j2 As Integer
        
        For j2 = I + 1 To wielkosctabeli - 1
            Dim promissin As Boolean
            promissin = Proc(newbest, j2, L, count, A)
            If Not promissin Then
                Exit For
            End If
        Next j2
        Proc = True
    End Function

Upvotes: -1

amit
amit

Reputation: 178521

This is a variation of subset-sum problem, the answer to the classic problem involving only integers is pretty easy using DP, and can be found in many threads around StackOverflow, like this one.

However, there is a small tweak in your problem that makes it just slightly different from the classic integer subset-sum problem - you are dealing with values that don't have to be integers, they also have a decimal value.

It seems that in your case, the decimal value is up to 2 digits "after the dot". This means, you can easily transform your problem into a classic integers subset-sum problem by simply multiplying all your values in the array by 100, and search for 100*x instead of x.
In your example - you will need to look for 12,369 in the array of integer values {123, 345, 2011, 10013, 20008}.

Attachment 1: Solving SubsetSum Problem for integers:
This is done using Dynamic Programming, where the recursive formulas for the DP is:

f(x,0) = FALSE if x<0
f(0,0) = TRUE
f(x,i) = f(x,i-1) OR f(x-arr[i], i-1)

By calculating the above bottom-up, you get a matrix of size (W*100+1) x (n+1) (where W is your requested sum and n is the number of elements in the array).

By searching for the column in the LAST row that holds the value true when you are done - you found the "best" possible sum that is up to your number.

Attachment 2: Finding the actual subset of numbers.
By now, you have found the best sum you can get, but not the best numbers yet. In order to do so, you will need to use your matrix (which you calculated previously), and replay the steps you did in order to generate this sum. This is explained for a similar problem in this thread, and in nutshell it is done by:

line <- BEST //best solution found
i <- n
while (i> 0):
  if table[line-array[i]][i-1] == TRUE:
      the element 'i' is in the set
      i <- i-1
      line <- line-array[i]
  else:
      i <- i-1

Note: If this is too complex, and the size of your arrays is fairly small, or alternatively the "2 decimals after the dot" restriction is not true - you pretty much have to use an exponential solution - brute force, which creates all possible subsets, and chooses the best out of them. There is no (known) efficient solution in this case because this problem is known to be NP-Hard

tl;dr: Multiply all values by 100, and then use an existing integers subset-sum problem algorithm to find the best fit.

Upvotes: 6

Related Questions