How to calculate the Upper Bound in 0-1 Knapsack problem
How to calculate the Upper Bound in 0-1 Knapsack problem. It is very simple. Example: 1. Calculate Profit/weight to know each profit of each weight 2. Sort Profit/weight by descending 8/5=1.65 11/7=1.57 6/4=1.5 4/3=1.3 3. Add each item once (due to 0-1 Knapsack problem) from the top of the list Profit = 8+11 Weight = 5+7 Knapsack's capacity is 14. To now those takes 5+7=12. So it only has 2 spare weight. Third item has 4 weight and 6 profit. Make it fraction so it's profit goes 6*1/2 = 3 (third item's profit) Profit = 8+11+3=22 Weight = 5+7+2=14 The possible maximum profit (in the situation of fraction available) is 22. 22 is the Upper Bound. Ref: http://math.stackexchange.com/questions/1267331/0-1-knapsack-upper-bound