Greedy Algorithm and Knapsack problems

 

Greedy Algorithm and Knapsack problems

Greedy Algorithm is used to solve knapsack problem.Fractional knapsack problem in which fractions of items can be taken rather than having to make a binary(0-1) choice for each item. 

We want to pack n items in Luggage

The ith item is worth v_i  dollars and w_i  weight pounds.Take as valuable a load as possible but cannot exceed W pounds.

Fractional knapsack problem

If w of item j is removed from the optimal load the remaining load must be the most valuable load weighting at most W-w that can be taken from other n-1 items plus wj  -w of item j.

• Compute the value per pound v_{i /}w_i for each item.
• Obeying a greedy strategy take as much as possible of  the item with the greatest value per pound.
• If the supply of that item is exhausted and can still carry more take as much as possible of the item with the next value per pound and so forth until we cannot carry any more.
• Sorting the items by value per pound the greedy algorithm in O(nlgn) time. 

Algorithm Fractional Knapsack problem

Fractional Knapsack(Array v,Array w,int W)

Step1:  For i=1 to Size(v).

Step2:  Do p[i]=v[i]/w[i].

Step3: Sort Descending(p)

Step4: i←1.

Step5: While(W>0)

Step6: Do amount=min(W,w[i])

Step7: solution[i]=amount.

Step8: W=W-amount.

Step9: i←i+1.

Step10: return solution.

Example

Consider 5 items along their respective weights and values

I=<I1,I2,I3,I4,I5>

w=<5,10,20,30,40>

v=<30,20,100,90,160>

The capacity of knapsack W=60.Find the solution to the fractional knapsack problem.

Solution

Item            w_{i                    vi                     pi=} v[i]/w[i].

I1                5                   30                  6

I3               20                 100                 5   

I5               40                 160                 4

I4               30                  90                  3    

I2               10                  20                  2   

Now fill knapsack according to the decreasing value of pi.

First choose item I1 whose weight is 5 then choose item I3 whose weight is 20.Now the total weight of knapsack is 5+20=25.  

Now the next item is I5 and its weight is 40 but we want only 35.So we choose fractional part of I5.

The value of fractional part of I5 is 

160/40*35=140.

Thus the maximum value is =30+100+140=270.