aspose file tools*
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
Author

optimal way to grab closest sum

omar bili
Ranch Hand

Joined: Aug 13, 2004
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

Joined: Jan 10, 2002
Posts: 60992
    
  65

Moved to Java in General (intermediate)


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

Joined: Oct 14, 2005
Posts: 18541
    
    8

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?
thanks
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: http://aspose.com/file-tools
 
subject: optimal way to grab closest sum