variant of knapsack problem

I have 'n' number of amounts (non-negative integers). My requirement is to determine an optimal set of amounts so that the sum of the combination is less than or equal to a given fixed limit and the total is as large as possible. There is no limit to the number of amounts that can be included in the optimal set.

for sake of example: amounts are 143,2054,546,3564,1402 and the given limit is 5000.

As per my understanding the knapsack problem has 2 attributes for each item (weight and value). But the problem stated above has only one attribute 开发者_Go百科(amount). I hope that would make things simpler? :)

Can someone please help me with the algorithm or source code for solving this?

this is still an NP-hard problem, but if you want to (or have to) to do something like that, maybe this topic helps you out a bit:

find two or more numbers from a list of numbers that add up towards a given amount

where i solved it like this and NikiC modified it to be faster. only difference: that one was about getting the exact amount, not "as close as possible", but that would be only some small changes in code (and you'll have to translate it into the language you're using).

take a look at the comments in my code to understand what i'm trying to do, wich is, in short form:

• calculating all possible combinations of the given parts and sum them up
• if the result is the amount i'm looking for, save the solution to an array
• at least, sort all possible solutions to get the one using the least parts

so you'll have to change:

• save a solution if it's lower than the amount you're looking for
• sort solutions by total amount instead of number of used parts

The book "Knapsack Problems" By Hans Kellerer, Ulrich Pferschy and David Pisinger calls this The Subset Sum Problem and dedicates an entire chapter (Ch 4) to it. The chapter is very comprehensive and covers algorithms as well as computational results.

Even though this problem is a special case of the knapsack problem, it is still NP-hard.