Algorithm to take the best set of numbers to sum

Question

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?

This is the [Subset Sum Problem](http://en.wikipedia.org/wiki/Subset_sum_problem). There are plenty of questions about it in this site. — amit, Dec 16 '14 at 08:56

score 6 · Accepted Answer · edited Jun 20 '20 at 09:12

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.

@IvayloStrandjev The same? It's a pretty long post, hope you were only at its beginning :S — amit, Dec 16 '14 at 10:00
actually only up until `Attachment 1` and I was about to post it :) I was about to make OP finish of the second attachment. — Ivaylo Strandjev, Dec 16 '14 at 10:03
The only change is that my actual problem is the decimal value is up to 4 digits "after the dot". Will it be possible to use your idea also here? It will be like 30-40 numbers to check with one greater. Let's say i have like 5 minutes to do so. Will it be possible? — Whencesoever, Dec 16 '14 at 10:29
@JanWalczak what are the values? For up to ~50,000 you should be fine I believe. — amit, Dec 16 '14 at 10:31
@amit yeah. U mean before *10000 multiplation? They should not be greater than 50,000. But after, they will be 500000000 : ). — Whencesoever, Dec 16 '14 at 10:35
@JanWalczak 500,000,000 should be fine, the problem is the *40 I forgot to add, I am pretty sure for the scale of values of ~10k it should work in under 5 minutes, but you will have to check it out and optimize it as much as you can. Unfortunately the problem is NP-Hard, so there is no known 'efficient' solution to it. — amit, Dec 16 '14 at 10:41

score -1 · Answer 2 · edited Apr 25 '21 at 09:33

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

Algorithm to take the best set of numbers to sum

2 Answers2