PDA

View Full Version : (C++) Unbounded Knapsack Problem



Beezleray
April 7th, 2009, 06:31 AM
Hi,
I'm trying to find an algorithm that helps solve an Unbounded Knapsack problem in C++, but I'm having trouble. Any help at all would be great!
Thanks!

EDIT:
I've tried using the Greedy Algorithm but it doesn't get the exact solution, close but not right.

Arndt
April 7th, 2009, 08:33 AM
Hi,
I'm trying to find an algorithm that helps solve an Unbounded Knapsack problem in C++, but I'm having trouble. Any help at all would be great!
Thanks!

EDIT:
I've tried using the Greedy Algorithm but it doesn't get the exact solution, close but not right.

Do you just need an existing solver, in any language, or does it have to be C++, or do you want to write one yourself? Wikipedia has a reference to an existing one in CAML.

When you say the greedy algorithm doesn't get the exact solution, how do you know there is a better solution?

Tony Flury
April 7th, 2009, 10:42 AM
From reading wikipedia myself it does not look like it has a algorithm that gets a perfect solution. Many maths problems (such as the Travelling salesman for instance) are like this.

The Greedy Algorithm may be the best you get, in that it gets you a good approximation to the right answer, but in some case it might be sub-optimal.

And as Arndt says - if you know that the Greedy Algorithm does not always give the best answer - how do you know ?

Beezleray
April 7th, 2009, 10:47 AM
Do you just need an existing solver, in any language, or does it have to be C++, or do you want to write one yourself? Wikipedia has a reference to an existing one in CAML.

When you say the greedy algorithm doesn't get the exact solution, how do you know there is a better solution?

Well I know the math for the most part(that's how I know the greedy algorithm isn't working) I just don't know how to implement it in C++. I would like to be able to figure out how to write it myself, (and in ways an existing solver could help me learn) basically I have two arrays one with the price and one with the weight, I know how much it can hold and I have any number of those items. I just can't seem to figure out how to iterate through correctly to find the best possible solution.

Zugzwang
April 7th, 2009, 11:03 AM
Well I know the math for the most part(that's how I know the greedy algorithm isn't working) I just don't know how to implement it in C++. I would like to be able to figure out how to write it myself, (and in ways an existing solver could help me learn) basically I have two arrays one with the price and one with the weight, I know how much it can hold and I have any number of those items. I just can't seem to figure out how to iterate through correctly to find the best possible solution.

As this looks like homework, I'm just giving you an example how iteration might work. Look at the following thread for an example:

http://ubuntuforums.org/showthread.php?t=846302&highlight=recursion

CptPicard
April 7th, 2009, 11:06 AM
I suppose you mean that you are trying with a small enough example that you can just manually construe the optimal solution or something, as there is no mathematical "closed form solution" or anything like that.

We're dealing with an NP-hard problem, so there is no known efficient (polynomial-time) exact algorithm. Trying is either a waste of time or makes you a huge genius if you succeed. :)

There is, however, the pseudo-polynomial DP algorithm for it that is mentioned in the wikipedia article... it is fairly easy to implement.

Or, you can always just simply brute force it.

sujoy
April 7th, 2009, 11:06 AM
you can calculate the ratio of price to weight for each object, sort it in descending order. and fillup the knapsack with as much of the highest ratio object as you can (in whole numbers) and move on to the next object with the highest ratio.

Zugzwang
April 7th, 2009, 11:15 AM
you can calculate the ratio of price to weight for each object, sort it in descending order. and fillup the knapsack with as much of the highest ratio object as you can (in whole numbers) and move on to the next object with the highest ratio.

..which is (almost) the greedy algorithm that the OP mentioned and not wanted.

Hint to the OP: You may also try to reduce the problem to SAT solving or something similar if you really want the precise solution. As CptPicard wrote, there's of course no guarantee that this (or any solution, provided that NP!=P) works fast, but it might work fast enough for you on the problem instances you are concerned with. "Branch&Bound" is also a concept you should look up for ideas how to implement a solver for this problem.

Beezleray
April 7th, 2009, 03:09 PM
Thanks for your help guys, its greatly appreciated!

P.S.
Its not homework, just a fun little side project (http://www.facebook.com/careers/puzzles.php?puzzle_id=2) to help learn the language.