Write an algorithm for Knapsack problem using greedy approach with suitable example.

Q.1

Algorithm:

Knapsack_algo(W,n)

{

            for i:1 to n do

            {

                        if(w[i]<W)then

                        {

                                    x[i]:=1.0;

                                    W=W-w[i];

                        }

            }

            if(i<=n)then

                        x[i]:=W/w[i];

}

Example:

Consider the item along with their respective weight and values.

I={I1,I2,I3}        w={5,4,3}               v={6,5,4}

Knapsack maximum weight, W=7.

Solution:

In this fractional crieteria items are arranged by certain ratio, where the ratio is value over profit(pi).Here solution proceed from maximum ratio to the minimum ratio.

Item	Value(vi)	Weight(wi)	Pi=(vi/wi)
I1	6	5	1.2
I2	5	4	1.25
I3	4	3	1.33

Now, arranging all the items according to their profit(pi)from maximum to minimum:

Item	Value(vi)	Weight(wi)	Pi=(vi/wi)
I3	4	3	1.33
I2	5	4	1.25
I1	6	5	1.2

Maximum weight that can be inserted is 7.SO,items I3 & I2 can be easily inserted.when item I1 is inserted, overflow occurs. So, it cannot be inserted.

So, maximum profit obtained is 4+5=9.