This week's book giveaway is in the OO, Patterns, UML and Refactoring forum. We're giving away four copies of Refactoring for Software Design Smells: Managing Technical Debt and have Girish Suryanarayana, Ganesh Samarthyam & Tushar Sharma on-line! See this thread for details.

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.

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

posted

0

is there a java implementation of this algorithm? thanks