> If the weight vector is w and the value vector is v, and there are n > items, the page shows that maximizing s=w (+/ .*) v subject to the > constraint s<:W. The algorithm given is dynamic programming, essentially > memoizing recursion, and shows this has asymptotic complexity > O(W*n), and so is in P.
For computational complexity usually the size of the input is considered. Since the size of W is 2^.W (number of bits needed to represent W), the dynamic programming solution does not demonstrate that integer knapsack is in P. ----- Original Message ----- From: John Randall <[EMAIL PROTECTED]> Date: Thursday, July 12, 2007 3:20 Subject: [Jgeneral] Re: [Jprogramming] packing problem To: General forum <[email protected]> > > Raul Miller wrote: > > W is the maximum allowed weight -- it has nothing to do with value > > in the problem described at > > http://cgm.cs.mcgill.ca/~msuder/courses/360/lectures/integer- > knapsack.html> > > > > At least as I understand it, W=8 means that the knapsack can hold > > up to 8 weight units. And, with n=3, w1=1, w2=2 and > w3=3, the knapsack > > will hold six weight units with all three objects in the > knapsack. As > > none > > of the values are negative, this also corresponds to the > maximum value > > the knapsack can hold. It's true that the value of the > contents of the > > knapsack would be 8, but these are value units and not weight units. > > > > If the weight vector is w and the value vector is v, and there > are n > items, the page shows that maximizing s=w (+/ .*) v subject to the > constraint s<:W. The algorithm given is dynamic > programming, essentially > memoizing recursion, and shows this has asymptotic complexity > O(W*n), and > so is in P. > > Whether this is a good way of solving a small case is not addressed. > For example, O(n log n) heapsort is going to be beaten by O(n^2) > insertion sort on an array of size 10. > > I thought this solved the restaurant problem: w is the cost of each > appetizer, v is the number of each you order, and W is the > amount of > money you have. You are trying to find s (and v), and in > particularshow that s=W. > > You are restricting to the case where v has entries 0 or 1, > which does > not seem to solve the problem. > > > > What I was taking as a general statement about the > > integer knapsack problem was actually a statement > > about the properties of a specific [very bad] algorithm. > > I don't see what is so bad about the algorithm described in Step > 3 of > the page: it shows that the problem is in P, which I thought was your > original question. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
