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 particular show 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. Best wishes, John ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
