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 20 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).

 

 

 

Contributor's Info

Created:
0Comment
Job sequencing with deadlines

The problem can be defined as, we are given a job set consisting n jobs where each job i, is associated with allowable time to complete is called deadline denoted by di and cost value called profit Pi . A profit Pi is earned if the ith job is completed with its deadline; we have to find the maximum number of jobs that can be solved within the deadline. The maximum P earned is the sum of profit value of the individual job in the job set. The optimal is a feasible solution with the maximum profit P. If the job is not completed by its deadline then the completion of the job does not yield any profit.

Find the feasible solution for the following list of job, also find the total profit earned assume that each job needs one unit of time in a single machine.

 

each job needs one unit of time in a single machine.

 JOBS

      J1

    J2

         J3

      J4

       J5

PROFITS

     2

     4

          3                 

      1                   

       10

DEADLINES

     3

     3

         3                           

       4                     

       4

 

Feasible solutions can be obtained step by step as follows, firstly sort the profit in descending order.

STEP-1 Create an array whose size is equal to the maximum deadline.

Max deadline of all the deadline= max(3,3,3,4,4) = 4. Therefore, 4-time slots will be there that is almost 4 jobs will be completed within their deadline.

 

 

 

 

 

0                                   1                                       2                                        3                                      4

Step-2  Sort all the jobs, choose the job according to the  highest profit and place in its deadline one by one in descending order,

i)  In the above job sequence, J5 has the highest profit.

 

 

 

 

 

J5

 0                                 1                                        2                                        3                                      4

 

ii)

 

 

 

 

    J2

 

 J5

0                                  1                                        2                                         3                                      4

 

iii)

 

 

 

   J3

 

    J2

 

 J5

0                                    1                                       2                                         3                                     4

 

iv)

 

    J2

 

   J3

 

    J2

 

 J5

0                                   1                                         2                                       3                                      4

 

 

Therefore, the highest profit in the given problem = J5  ,J2  , J3 , J1

                                                                                                              = 10+4+3+2

                                                                                                       = 19

Contributor's Info

Created: Edited:
0Comment