This discussion is archived
1 Reply Latest reply: Jan 29, 2010 5:34 AM by 843853 RSS

Knapsack

843853 Newbie
Currently Being Moderated
Hi!

I have heard of the knapsack problem and I wanted to try to solve it. According to wikipedia, an algorithm to solve the knapsack problem should decide the number of each item to bring. http://en.wikipedia.org/wiki/Knapsack_problem

In this example http://www.cs.princeton.edu/introcs/96optimization/Knapsack.java.html that shows dynamic programming, the program does not determine how many of each item to bring, just if they should be brought or not.

Is this example not a complete algorithm to solve the problem? Or have I misunderstood wikipedia?
  • 1. Re: Knapsack
    843853 Newbie
    Currently Being Moderated
    There are variations of the knapsack problem. The example code solves the 0/1 knapsack problem which has the constraint that an item can be added at most once. So it does determine how many of each item to bring: take is 1, don't take is 0.

    The unbounded knapsack problem is another problem which can give a different result. This would need a different algorithm than the one in the example.

    The problem can also be given as a decision problem which simply requires a true or false answer. But getting the list of items from an algorithm that solves the decision problem is usually a trivial change.