 |  |  |  |  |  |  |  |
wired knapsack...
Please support our C++ advertiser: Intel Parallel Studio Home
 |
•
•
Join Date: Jun 2008
Posts: 86
Reputation: 
Solved Threads: 5
Junior Poster in Training
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!!
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!! 
•
•
Join Date: Aug 2005
Posts: 15,378
Reputation: 
Solved Threads: 1466
why use recursion when a simple loop will do. Loops are always faster than recursion (and less memory/stack intensive too).
Don't PM me with questions -- you might get a nasty PM in response. If you have a question then post it in one of the forums.
•
•
Join Date: Jun 2008
Posts: 86
Reputation:
Solved Threads: 5
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.
•
•
Join Date: Jan 2008
Posts: 3,813
Reputation:
Solved Threads: 501
•
•
•
•
Originally Posted by 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.
C++ Syntax (Toggle Plain Text)
I have no idea if this is all you are looking for. This comment:
•
•
•
•
Originally Posted by gregorynoob
would have to check all the combinations, also i didn't say, there are no unlimited supplies of items like in usual knapsack.
•
•
Join Date: Jun 2008
Posts: 86
Reputation:
Solved Threads: 5
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.
•
•
Join Date: Dec 2006
Posts: 1,089
Reputation:
Solved Threads: 164
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-P.../dp/0321534964 would be the definitive reference.
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-P.../dp/0321534964 would be the definitive reference.
•
•
Join Date: Jan 2008
Posts: 3,813
Reputation:
Solved Threads: 501
•
•
•
•
Originally Posted by 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-P.../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.
|
Other Threads in the C++ Forum
- Previous Thread: document-view or non document-view architecture?
- Next Thread: ascii converter
| Thread Tools | Search this Thread |
You need to join our community in order to build your list of favorite forums. You can visit the forum index for a listing of all forums.
Related Forum Features
Latest C++ Posts
- Today's Posts
- Unanswered Threads
api array beginner binary bitmap c++ c/c++ calculator char char* class classes coding compile compiler console conversion count data database delete desktop developer directshow dll download dynamic email encryption error file forms fstream function functions game getline google graph gui homeworkhelper iamthwee ifstream input int integer java lib linkedlist linker linux loop looping loops map math matrix memory multiple news node number numbertoword output parameter pointer problem program programming project proxy python random read recursion recursive reference return rpg sorting string strings struct template templates test text text-file tree unix url vector video visualstudio win32 windows winsock word wordfrequency wxwidgets
