943,915 Members | Top Members by Rank

Software Development > C++ > wired knapsack...
Ad:
  • C++ Discussion Thread
  • Unsolved
  • Views: 2311
  • C++ RSS
Permalink
Sep 27th, 2008
0

wired knapsack...

Expand Post »
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!!
Reputation Points: 12
Solved Threads: 5
Junior Poster in Training
gregorynoob is offline Offline
86 posts
since Jun 2008
Permalink
Sep 27th, 2008
0

Re: wired knapsack...

why use recursion when a simple loop will do. Loops are always faster than recursion (and less memory/stack intensive too).
Sponsor
Team Colleague
Featured Poster
Reputation Points: 5608
Solved Threads: 2282
Retired and Enjoying Life
Ancient Dragon is offline Offline
21,953 posts
since Aug 2005
Permalink
Sep 27th, 2008
0

Re: wired knapsack...

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.
Reputation Points: 12
Solved Threads: 5
Junior Poster in Training
gregorynoob is offline Offline
86 posts
since Jun 2008
Permalink
Sep 27th, 2008
0

Re: wired knapsack...

Click to Expand / Collapse  Quote 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.
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?

C++ Syntax (Toggle Plain Text)
  1. int items[200];
  2. int x; // number of items to add.
  3.  
  4. // code to fill in above variables
  5. int sum = 0;
  6. for (int i = 0; i < x; i++)
  7.      sum += items[i];

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

Click to Expand / Collapse  Quote 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.
suggests there is more to the problem, but I don't know what you mean. Can you elaborate on the assignment?
Featured Poster
Reputation Points: 2614
Solved Threads: 687
Posting Expert
VernonDozier is offline Offline
5,375 posts
since Jan 2008
Permalink
Sep 27th, 2008
0

Re: wired knapsack...

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.
Reputation Points: 12
Solved Threads: 5
Junior Poster in Training
gregorynoob is offline Offline
86 posts
since Jun 2008
Permalink
Sep 28th, 2008
0

Re: wired knapsack...

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.
Reputation Points: 1159
Solved Threads: 285
Posting Virtuoso
vijayan121 is offline Offline
1,606 posts
since Dec 2006
Permalink
Sep 28th, 2008
0

Re: wired knapsack...

Click to Expand / Collapse  Quote 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.
Featured Poster
Reputation Points: 2614
Solved Threads: 687
Posting Expert
VernonDozier is offline Offline
5,375 posts
since Jan 2008

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in C++ Forum Timeline: document-view or non document-view architecture?
Next Thread in C++ Forum Timeline: ascii converter





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC