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}

  • 1
    This seems to be a simple form of the [knapsack problem](http://en.wikipedia.org/wiki/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).2012-01-08
  • 0
    Check out Wikipedia article on [subset sum problem](http://en.wikipedia.org/wiki/Subset_sum_problem), and the book *Approximation Algorithms* by Vijay V. Vazirani.2012-01-08
  • 0
    Please anwer your own question, and accept it to close the issue.2013-02-10

1 Answers 1