On 7/11/07, John Randall <[EMAIL PROTECTED]> wrote:
Raul Miller wrote:> > 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.
The optimal solution can have a higher weight than B: you are not taking
into account the values.
Suppose n=3, w1=1, w2=2, w3=3, W=8. Then the weight of B is 6. However,
W can be achieved with (for example) v1=2, v2=0, v3=2.
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.
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
