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!!
gregorynoob
2
Junior Poster in Training
Recommended Answers
Jump to Postwhy use recursion when a simple loop will do. Loops are always faster than recursion (and less memory/stack intensive too).
Jump to Posta 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 …
All 6 Replies
Ancient Dragon
5,243
Achieved Level 70
Team Colleague
Featured Poster
why use recursion when a simple loop will do. Loops are always faster than recursion (and less memory/stack intensive too).
gregorynoob
2
Junior Poster in Training
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
2,218
Posting Expert
Featured Poster
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
2
Junior Poster in Training
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
1,152
Posting Virtuoso
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
2,218
Posting Expert
Featured Poster
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.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.