jQuery in Action, 3rd edition
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

Win a copy of OCA Java SE 8 Programmer I Study Guide this week in the OCAJP 8 forum!
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: 63348

Moved to Java in General (intermediate)

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

Joined: Oct 14, 2005
Posts: 19742

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: http://aspose.com/file-tools
subject: optimal way to grab closest sum
It's not a secret anymore!