File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Java in General and the fly likes optimal way to grab closest sum Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "optimal way to grab closest sum" Watch "optimal way to grab closest sum" New topic

optimal way to grab closest sum

omar bili
Ranch Hand

Joined: Aug 13, 2004
Posts: 177
i have a group of items, stored in an array, sorted according to the influence:

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

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

Joined: Jan 10, 2002
Posts: 62279

Moved to Java in General (intermediate)

[Asking smart questions] [Bear's FrontMan] [About Bear] [Books by Bear]
Paul Clapham

Joined: Oct 14, 2005
Posts: 19357

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

Joined: Aug 13, 2004
Posts: 177
is there a java implementation of this algorithm?
Rusty Shackleford
Ranch Hand

Joined: Jan 03, 2006
Posts: 490
You can google for it, or just write your own.

"Computer science is no more about computers than astronomy is about telescopes" - Edsger Dijkstra
I agree. Here's the link:
subject: optimal way to grab closest sum