http://cgm.cs.mcgill.ca/~msuder/courses/360/lectures/integer-knapsack.html
I think I see a problem with that page. It states: If the weight of B is less than W, then Knapsack-Value(B,W) solves at least 2n subproblems. Thus, Knapsack-Value(B,W) has exponential running time in the worst case. But if the weight of B is less than W, then every object in the problem set can be placed in the knapsack and the problem can be solved trivially. Moreover, if W is slighly less than the weight of B, then the problem can be approached in reverse (minimizing the value of a weight which exceeds weight(B)-W). There might be a knapsack problem here, but if so it's not being presented very clearly. -- Raul ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
