Algorithm to get closest number set

[SonicWave]

Good day,

Let say we hv a number set {11, 22, 33, 44, 55, 66, 77, 88, 99, 111}. Is there any algorithm that can give me a subset {x1, x2, x3, ...} where the sum of the subset closest and less than to 150 , for example ?

E.g.,

11+22 = 33
11+22+33+44 = 110
11+22+33+44+55 = 165

So the answer using the above example would be {11, 22, 33, 44} as it gives the closest 10 150. Is there any algorithm to get this set ?

Thanks.

SonicWave :confused:

[Guitarism]

this is probably way too messy and can be done better BUT


Dim answer As String
Dim counter As Integer
Dim sum As Integer
Dim goal As Integer
Dim i As Integer
Dim myArray(10) As Integer
myArray(0) = 11
myArray(1) = 22
myArray(2) = 33
myArray(3) = 44
myArray(4) = 55
myArray(5) = 66
myArray(6) = 77
myArray(7) = 88
myArray(8) = 99
myArray(9) = 111
counter = 0
sum = 0
goal = 150
answer = ""
i = 0

Do While counter < (UBound(myArray()) - 1)
sum = sum + myArray(counter)

If sum = goal Then
Do While i <= counter
answer = answer & " " & myArray(i)
i = i + 1
Loop

MsgBox ("{" & answer & "}" & " added together = " & sum & " which is closest to and less than " & goal)
Exit Do
End If

If sum > goal Then
sum = sum - myArray(counter)
Do While i <= counter
answer = answer & " " & myArray(i)
i = i + 1
Loop
MsgBox ("{" & answer & "}" & " added together = " & sum & " which is closest to and less than " & goal)
Exit Do
End If
counter = counter + 1
Loop

[Logophobic]

Is it necessary that your subset contain only consecutive members of the number set?

If not, then the solution for the example number set and target sum is:
11 + 22 + 111 = 144
33 + 111 = 144

A simple recursive subroutine can easily find all these sums.

[Guitarism]

I think so Logo; the way he gives examples shows that.

Also "subset {x1, x2, x3, ...} " implies consecutive members.

[NotLKH]

But must the first element of the subset be the first element of the set?

In other words, could {66 77} be considered?