wired knapsack...

[gregorynoob]

ok, so this is my problem...
i have an array of items, which i want to sum to x or above in a most efficient way...
is there a way for doing this? cause all the values are 64 bit ints.
i tried recursion but it's slow cause i can have up to 200 items :( helppp!!

[Ancient Dragon]

why use recursion when a simple loop will do. Loops are always faster than recursion (and less memory/stack intensive too).

[gregorynoob]

a simple loop? could you please tell me what algorithm would that be? cause recursion would go O(n!), would have to check all the combinations, also i didn't say, there are no unlimited supplies of items like in usual knapsack.

[VernonDozier]

a simple loop? could you please tell me what algorithm would that be? cause recursion would go O(n!), would have to check all the combinations, also i didn't say, there are no unlimited supplies of items like in usual knapsack.

O (n!) when using recursion? I either don't understand the problem correctly or I think you are doing an extremely inefficent recursion. Post your recursion code. As for the simple loop, if I'm understanding correctly, you would just do something like this?

int items[200];
int x; // number of items to add.

// code to fill in above variables
int sum = 0;
for (int i = 0; i < x; i++)
     sum += items[i];

I have no idea if this is all you are looking for. This comment:

would have to check all the combinations, also i didn't say, there are no unlimited supplies of items like in usual knapsack.

suggests there is more to the problem, but I don't know what you mean. Can you elaborate on the assignment?

[gregorynoob]

well i guess it can really be done without DP, as it is not really limited and can be done by going through the sorted array of items from the end to the start, if an item is larger than limit, limit is set to zero and i break the loop, otherwise i subtract the item value from the limit and keep on going. i guess that was what Dragon meant.

[vijayan121]

the general knapsack problem and the subset sum problem are NP-hard, but not NP-incomplete. so there are no polynomial-time algorithms. but it is one of the easy NP-complete problems to solve.

it can be solved (in pseudo-polynomial time) using dynamic programming.

AFAIK, using a Branch and bound algorithm http://en.wikipedia.org/wiki/Branch_and_bound should yield a faster solution. perhaps, you should use a recursive (rather than iterative) Branch and bound. iteration won't give you any significant improvement in performance here.

knuth volume 4 http://www.amazon.com/Art-Computer-Programming-Fascicle-Combinatorial/dp/0321534964 would be the definitive reference.

[VernonDozier]

the general knapsack problem and the subset sum problem are NP-hard, but not NP-incomplete. so there are no polynomial-time algorithms. but it is one of the easy NP-complete problems to solve.

it can be solved (in pseudo-polynomial time) using dynamic programming.

AFAIK, using a Branch and bound algorithm http://en.wikipedia.org/wiki/Branch_and_bound should yield a faster solution. perhaps, you should use a recursive (rather than iterative) Branch and bound. iteration won't give you any significant improvement in performance here.

knuth volume 4 http://www.amazon.com/Art-Computer-Programming-Fascicle-Combinatorial/dp/0321534964 would be the definitive reference.

Oh, this is a well known problem? I had never heard of it before and was just going from the description in the first post so I was a little puzzled. I just looked it up on wikipedia and it makes more sense now.