One more thing. I was wrong in the complexity calculation: the algorithm does run in exponential time, although it does not look like it.
The problem is that while the weight and value vectors depend on n, the maximum weight W does not, so the input size depends on n and log W. This means that O(nW) is exponential on the input size. I believe this type of algorithm is called pseudo-polynomial. Best wishes, John ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
