Knapsack Branch and Bound

Question

I have following data :

item   weight   value   value/weight
1      5        40      8
2      2        10      5
3      6        30      5
4      1        12      12
5      2        18      9

Capacity is 10. How to proceed with calculating upper bound for node 0? I'm calculating upper bound for node 0 as follows :

ub = v + [W-w] * [v/w]
ub = 0 + [10] * [8] = 80

Or do I need to sort the items in decreasing order of their value/weight as 12,9,8,5,5? and then calculate for upper bound? Or I'm doing it right, without sorting, calculating the upper bound and proceeding with next item?

In the method without sorting I'll not be getting the maximum upper bound at node 0, i think so.

ub = 0 + [10] * [12] = 120 // if sorted

Thanks already for your help.

Answer 1

The upper bound for node zero is the greedy solution to the fractional knapsack. Just take the element with highest value/weight ratio and keep inserting it until no space is left or you have inserted it completely. And repeat the process.