variant of knapsack problem

Question

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 (amount). I hope that would make things simpler? :)

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

It's bounded by the limit. So if n is reasonable, this can be solved quite quickly. (ie What's the maximum value of n?) — flight, Sep 08 '11 at 10:04
@Ricky Bobby -- true but the guy has to get as many items as possible into the knapsack (as I read it, anyway). Hmmmm. Well, maybe not. If the problem is to get as much *weight* into the knapsack as possible, then of course you are right. — Pete Wilson, Sep 08 '11 at 10:16
@jcs -- there are plenty of hints in these comments, so you should be able to do this problem easily. — Pete Wilson, Sep 08 '11 at 10:19
Just set value = weight in the standard knapsack problem if wou want to maximize weight. If you want to maximize number of items, set value = 1. — Jean-François Corbett, Sep 08 '11 at 10:44
@quasiverse -- there is no max limit of n, but i don't see it crossing 200. — jcs, Sep 08 '11 at 10:45
@Ricky Bobby -- the problem is to get as much _weight_ into the knapsack as possible and not as many items. — jcs, Sep 08 '11 at 10:47

score 1 · Accepted Answer · edited May 23 '17 at 12:29

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

score 0 · Answer 2 · answered Sep 08 '11 at 10:16

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.

variant of knapsack problem

2 Answers2