1
$\begingroup$

I need an effective algorithm to find a subset of integers within a set that meet the conditions:

  • The sum of sub-set items <= the "limit"
  • prefer to pick the subset with maximum values that fit the limit as close as possible.

Examples:
if the set after sort is {3,2,2} and "limit" is {4}, the subset would be {2,2}

if the set after sort is {3,2,2,1,1} and "limit" is {4}, the subset would be {3,1}

if the set after sort is {3,3,1} and "limit" is {5}, the subset would be {3,1}

  • 0
    Please anwer your own question, and accept it to close the issue.2013-02-10

1 Answers 1

1

Moving comments into the answer box, which the OP never did:

This seems to be a simple form of the knapsack problem. As you can see at the link, there are fairly good approximative solutions, but an exact solution will not be efficient (as it is NP-hard). – Marc van Leeuwen

Check out Wikipedia article on subset sum problem, and the book Approximation Algorithms by Vijay V. Vazirani. – user2468