How to calculate the Upper Bound in 0-1 Knapsack problem

By -
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

Comments

Post a Comment

Popular posts from this blog

Primal problem and Dual problem

By -
Image
When we face the problem that can be solved by the linear problem method, there will be provided two approaches solving the issues called first 'Primal problem' and second is 'Dual problem'. These two methods can be always introduced together against the problem. However it can different results and we call it 'Duality gap'. Primal problem is the original problem given. Dual problem is converted from the original by 'Lagrangian dual problem', 'Wolfe dual problem' or 'Fenchel dual problem'. As usual method 'Lagrangian dual problem' introduces a variable (gamma) having the positive value in order to add the equation into the object function and formulize it as Lagrangian format. And find the minimal value of Dual problem to find the solution of Primal problem. The result value of Primal and Dual problem can be different and we call it 'Duality gap'. Duality gap is always non-negative or zero. References http://m...
Read more

What is the Shadow price?

By -
The shadow price can be thought that is the profit increase by the resource increase. In other words on the decision making purpose if you want to know how much profit would increase depending on the resources invested or spends, then the shadow price shows the level of profit increase from that. I believe there provide great explanation on the internet enough so wouldn't describe here more but for Korean here translated for those. 섀도우 금액은 자원의 추가 투자 또는 소비에 대해 늘어나는 단위 이익을 말한다.
Read more

Why a negative coefficient of variable means it is not optimal in simplex method?

By -
Why a negative coefficient of variable means it is not optimal in Simplex method? Which means why we should make all coefficient non-negative(positive) for optimization of MAX linear programming problem? When we have the following MAX problem. MAX 3x + 5y This can be transformed to the Standard form: z - 3x - 5y As long as we have a negative coefficient in this standard form equation then there is still a way to increase 'z' value by increasing 'x', 'y' as well. However, when having positive one : z + 3x +5y then there is no way to increase 'z' value unless 'x' or 'y' has a negative value. Which is not available by the condition: S.T. x, y >0 Therefore, in order to find the optimum solution of MAX problem, we only need to make sure all coefficients are positive of Objective Function equation.
Read more