Knapsack problem with the greedy approach

Lets try to apply the greedy method to solves the knapsack problem.Suppose, object i has the weight w_i and the knapsack has the capacity m. If the fraction x_i which 0≤ x_i ≤ 1 is added to the knapsack then ultimately the profit p_ix_i earned. The objective of this is nothing but to maximizes the total number of profits that we earned. Since the knapsack capacity is m, we required all chosen object’s weight is at most m. Formally the problem can be stated as follows

The profits and weights are the positive numbers and the feasible solution is the any kind of set (x_i……..x_n) satisfying the above condition. Consider the following algorithm for more clear of the feasible solution.

Algorithm Greedysnap (m,n)

{

// p [1:n] and w [1:n] are the profits and weights respectively of n objects order.

// u = knapsack capacity ; m = knapsack size.

{

for i=1 to n do

x [i] = 0.00 ;     // initialized solution to zero.

u= m ;

for i=1 to n do

{

if w[i] > u then

Break;

x [i] =1.0;

u = u - w[i];

}

if (i ≤ n) then

x [i] = u / w [i];

         }

}

In the above algorithm at each step we involved object which has he maximum profit per unit of capacity used. This means that objects are considered in order of the ratio p_i / w_i.

Let’s consider the following instance of abstract problem n=3, m=20 and profits (p₁ p₂ p₃) = (25, 24, 15) and weights (w₁ w₂ w₃) = (18,15,10) and we have to find out most feasible solution.

Let (x₁ x₂ x₃) = ( 1/2, 1/3, 1/4); (1, 2/15, 0); (0, 1, 1/2) 

Solution 1: maximize the object function

Lets put the objects with the maximum profit in the knapsack and then use the fraction of last object to fill the knapsack to capacity.

 

 

This method does not give optimal solution.

Solution 2: maximize capacity

Choose object according to least weight. In the knapsack we can get the more object and increase profit.

Solution is still not optimal. Rate of profit is not high enough.

Solution 3: balancing profit and capacity

choose objects starting with the largest and working to smallest ratio.

Here we get the optimal solution. We achieve a balance between the rate at which profit increase with the rate at which the capacity is used.