KNAPSACK ALGORITHM BY GREEDY METHOD

Knapsack algorithm follows the greedy algorithm. Knapsack in simpler words means bag; the aim of this algorithm is to find the maximum value or maximum profit.

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Suppose, a person went to a shop with a bag of capacity 25kg, now in the shop, there are 6 various items along with price tags attached. Among those 6 items, he is free to choose as many items possible within 25kg, keeping weight and cost in mind, he will choose items in order to have maximum profit.

 

CRITERIA FOR FILLING THE KNAPSACK USING GREEDY

  1. Items are arranged in descending order of their values or cost. The object is to maximize the value.
  2. Items are arranged in ascending order of their weights. Objects are to maximize the number of items in the knapsack.
  3. Items are arranged in descending order of certain ratios  Pi  = Vi  / W i    where Vi is a value of item Ii  and Wi is the weight of item Ii.

ALGORITHM

Step-I Repeat for i=1 to n

  1. X[i]= 0

  2. W= Value
  3. V=0

Step-II Repeat for i=1 to n through step 4.

Step-III If I[i]>W goto step7.

Step-IV  If Wi> W

  1. X[i]=W/W[i]
  2. W=W-Xi *Wi
  3. V=V+V[i]*X[i]

Step-V 

  1. X[i]=1.0
  2. W=W-W[i]
  3. V=V+V[i]*X[i]

Step-VI Return V.

Step-VII Exit.

 

We are given a knapsack of 60 kgs. Find the feasible solution for the following  5 items where cost and weight of every item are given in the following table of items, also find the total profit earned.

 

      ITEMS

 

    I-1

 

       I-2

 

   I-3

 

        I-4

 

         I-5

 

    COST

 

  30

 

      40

 

   45

 

        77

 

         90

 

     WEIGHT

 

   5

  

 

     10

 

  15                 

 

        22

 

         25

 

Find feasible solutions for the following table given.

Using the three criteria, the items are arranged in descending order of certain ratios, Pi= Vi/Wi where Vi is the value of item Ii and Wi is the criteria of the item Ii.

Cost/Weight of every item= {30/5, 40/10, 45/15, 77/22, 90/25} = {6.0, 4.0,3.0,3.5,3.6}

Cost/ Weight arranged in descending order= {6.0, 4.0, 3.6,3.5,3.0}

 

      ITEMS

 

    I-1

 

       I-2

 

   I-5

 

        I-4

 

         I-5

 

    COST

 

  30

 

      40

 

   90

 

        77

 

         45

 

     WEIGHT

 

   5

  

 

     10

 

  25                 

 

        22

 

         15

 

Let Net profit P=0. Taking the items sequentially unit, the knapsack is filled, W=60kg

Taking I-1 ,  W=W-Xi *Wi = 60- 5*1 = 55

                     P= P + Ci * Xi = 0+ 30* 1= 0+30 = 30

Taking I-2, W=W-Xi *Wi = 55- 10*1= 45

                      P= P + Ci * Xi = 30+40*1=70

Taking I-5, W=W-Xi *Wi = 45-25*1=20

                      P= P + Ci * Xi=70+90*1=160

Taking item I-4, we see the item has weight 22kgs but knapsack requires only 20kgs. So a part of item I-4 will be considered i.e, X= 20/22

Taking I-4, W=W-Xi *Wi= 20-22*20/22= 0

                      P= P + Ci * Xi= 160+ 77*20/22= 160+70= 230

Hence, the knapsack has been filled up fully and profit earned is 230.

 

COMPLEXITY

Here we see that the items are considered based on the ratio value/weight in descending order.

Sorting P, profit in descending order in any suitable sorting algorithm requires big O(n log n) again in the above algorithm. We see, that filling the knapsack requires Big O in n times and the loop runs for Big O(n time). So the time complexity becomes Big O(n log n).

 

 

 

0Comment