understanding Knapsack upper bound

Question

I am interested in the knappsack problem and I want to solve it with a branch and bound algorithm.

I know that the upper bound can be calculated by sorting the items 1..n descending by value/weight ratio, finding the break item s (the first item that does not fit completely in the knapsack) and calculating the following:

(C is the capacity of the Knappsack,w(j) the weight of item j)

(Calculating the fraction of s that still fits in the knappsack)

(Sum up all values from the first s-1 items and add a fraction of the value of s)

However, what I don't understand is why we can round down the second part of the third equation still holding our upper bound.

I hope that someone would give me a hint, an explanation or some literature reference explaining that.

Answer 1

That literature assumes that all items have integral values. If that is the case, then obviously the maximum value is an integer, so the the upper bound can be rounded down to an integer.

If the values are real numbers, the rounding is not correct