Please disregard this. John had said the same thing between the msg I am responding to and my response.
----- Original Message ----- From: Roger Hui <[EMAIL PROTECTED]> Date: Thursday, July 12, 2007 8:17 Subject: Re: [Jgeneral] Re: [Jprogramming] packing problem To: General forum <[email protected]> > > 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
