understanding Knapsack upper bound

1.9k views Asked by At

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:

enter image description here (C is the capacity of the Knappsack,w(j) the weight of item j)

enter image description here (Calculating the fraction of s that still fits in the knappsack)

enter image description here (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.

1

There are 1 answers

0
Eric On BEST ANSWER

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