# optimal way to grab closest sum

omar bili
Ranch Hand
Posts: 177
hi,
i have a group of items, stored in an array, sorted according to the influence:
say

class person
name (string)
influence (number)
end class

i have a number x, i need to get a group of items where the sum of their influence is the closest to the given number x
example:

s1 70
s2 60
s3 25
s4 11

and x = 90:
so the result wil be s2 and s3 coz 70 + 25 = 95 is the closest sum to 90..
sorry for i dont know if such an algo has a name..
thanks for any help.

Bear Bibeault
Author and ninkuma
Marshal
Posts: 65229
95
Moved to Java in General (intermediate)

Paul Clapham
Sheriff
Posts: 21416
33
If you want to find a subset of the numbers such that their sum is the largest possible value no greater than the given number X, that's called the backpack problem. I imagine your problem is mathematically equivalent.

omar bili
Ranch Hand
Posts: 177
is there a java implementation of this algorithm?
thanks

Rusty Shackleford
Ranch Hand
Posts: 490