Analysis Design Of Algorithm (ADA) | Knapsack Problem Using Greedy Approach

📌Highlights: Hi friends! In this post I am  going to explain about Knapsack problem using Greedy approach. I am try to explain with the help of examples.

Knapsack Problem is an application of Greedy Strategy / Method. By Knapsack problem we will find maximum profit. There are so many solution to solve any problem but we will select those solution which generate maximum profit.

Let here we see what the knapsack problem says by the help of an example.

Suppose we have some objects and every object is associated to some profit(p) and weight (w).

Example 1: Find the optimal solution for knapsack problem for n=7 and m=15

Here, m=15 , n=7

Now here Profit is P and weight is W

suppose we have a bag or container which is filled by items / objects. Here  our main aim is to fill the container by objects if the number of items are more than the capacity of container than it is a problem , suppose here the capacity is m=15. Here we will fill items / objects in container in such as way that it should not exceed the given capacity i.e 15 we can also say that it is a constraint with this problem.

It is a optimisation problem. we have a lot of solution from this but we need optimal solution that have maximum result. This knapsack problem is for those item which we can divide. Here it not compulsory to  take complete weight of object.

There are so many way to select the object such as by maximum profit or by minimum weight but we will see which one is best.

Let, First we will calculate profit by weight, for example profit for 1kg item.

Now first we calculate profit by weight ratio i.e p/w. It is a maximum profit per item.

Item         1       2       3       4      5       6       7

P/W = { 10/2 , 5/3 , 15/5 , 7/7 , 6/1 , 18/4 , 3/1 }

P/W = {   5    ,  1.6 ,    3 ,   1  ,  6 ,    4.5  ,    3 }

Now we will put the items in the container such as:

Now we will select the items in order whose p/w ratio is maximum.

STEP-1:

Select first item from list and put into container is object 5 because its p/w value is highest i.e 6 . Here we can take the whole weight i.e 1 so mark as 1 unit 

we get

Item         1       2       3       4      5       6       7

P/W = { 10/2 , 5/3 , 15/5 , 7/7 , 6/1 , 18/4 , 3/1 }

P/W = {   5    ,   1.6 ,    3 ,   1  ,  6 ,    4.5  ,    3 }

y  =    {   -         -          -     -      1       -          -  } 

Note: y shows if the item is completely taken then it shows 1 or if item is taken partial then the value may be in fraction.

Capacity of container become (15-1) = 14

STEP-2:

Now select next item from list and put into container is object 1 because its p/w value is second highest i.e 5 . Here we can take the whole weight i.e 2 so mark as 1 unit . 

we get

Item         1       2       3       4      5       6       7

P/W = { 10/2 , 5/3 , 15/5 , 7/7 , 6/1 , 18/4 , 3/1 }

P/W = {   5    ,   1.6 ,    3 ,   1  ,  6 ,    4.5  ,    3 }

y =     {   1         -         -     -       1       -          - } 

Capacity of container become (14-2) = 12

STEP-3:

Now select next item from list and put into container is object 6 because its p/w value is next highest i.e 4.5 . Here we can take the whole weight i.e 4 so mark as 1 unit . 

we get

Item         1       2       3       4      5       6       7

P/W = { 10/2 , 5/3 , 15/5 , 7/7 , 6/1 , 18/4 , 3/1 }

P/W = {   5    ,   1.6 ,    3 ,   1  ,  6 ,    4.5  ,    3 }

y =     {   1         -        -      -      1        1        -  }

Capacity of container become (12-4) = 8

STEP-4:

Now select next item from list and put into container is object 3 because its p/w value is next  highest i.e 3 . Here we can take the whole weight i.e 5 so mark as 1 unit . 

we get

Item         1       2       3       4      5       6       7

P/W = { 10/2 , 5/3 , 15/5 , 7/7 , 6/1 , 18/4 , 3/1 }

P/W = {   5   ,  1.6 ,    3 ,   1  ,  6 ,    4.5  ,    3 }

y =     {   1       -         1     -     1        1        -  }

Capacity of container become (8-5) = 3

STEP-5:

Now select next item from list and put into container is object 7 because its p/w value is next  highest i.e 3 . Here we can take the whole weight i.e 1 so mark as 1 unit . 

we get

Item         1       2       3       4      5       6       7

P/W = { 10/2 , 5/3 , 15/5 , 7/7 , 6/1 , 18/4 , 3/1 }

P/W = {   5    ,  1.6 ,    3 ,   1  ,  6 ,    4.5  ,    3 }

y =     {   1          -       1            1        1      1  }

Capacity of container become (3-1) = 2

STEP-6:

Now select next item from list and put into container is object 2 because its p/w value is next  highest i.e 1.3 . Here THE  weight is 3 but we have space for item upto weight 2 so we will 2/3 from 3 and mark as 2/3 unit . 

we get

Item         1       2       3       4      5       6       7

P/W = { 10/2 , 5/3 , 15/5 , 7/7 , 6/1 , 18/4 , 3/1 }

P/W = {   5    , 1.6 ,    3 ,    1  ,   6 ,     4.5  ,    3 }

y =     {   1       2/3        1      0      1        1        1  }

Capacity of container become (2-2) = 0

Now we see our container is full of item there is no space for remaining item so we left remaining items such as item 4 will left due to no space so we put value of x(capacity of container)=0.

Now here y always lies between 0 and 1 (0<=y<=1)

Now find total profit:

Total profit: y_ip_i

=  1 X 10 + 2/3 X 5 + 1 X 15 + 0 X 7 + 6 X 1 + 1 X 18 + 3 x 1

= 10 + 10/3 + 15 + 0 + 6 +18 + 3

= 55.3

 Now we can say that this method give us maximum profit of 55.3.

Implementation of Knapsack Problem Using Greedy Method

Copy Text

#include <stdio.h>

void main()

{

    int m, n, cur_weight, item;

    //m(capacity),n(number of items)

    int used[10];

    float total_profit;

    int i;

    int w[10];//weight

    int p[10];//profit

    printf("Enter the capacity of knapsack:\n");

    scanf("%d", &m);

    printf("Enter the number of items:\n");

    scanf("%d", &n);

    printf("Enter the weight and profit of %d item:\n", n);

    for (i = 0; i < n; i++)

    {

        printf("Weight[%d]:\t", i);

        scanf("%d", &w[i]);

        printf("Value[%d]:\t", i);

        scanf("%d", &p[i]);

    }

    for (i = 0; i < n; ++i)

        used[i] = 0;

    cur_weight = m;

    while (cur_weight > 0)

    {

        item = -1;

        for (i = 0; i < n; ++i)

            if ((used[i] == 0) &&

                ((item == -1) || ((float) p[i] / w[i] > (float) p[item] / w[item])))

                item = i;

        used[item] = 1;

        cur_weight -= w[item];

        total_profit += p[item];

        if (cur_weight >= 0)

            printf("Added object %d (%d Rs., %dKg) completely in the bag. Space left: %d.\n", item + 1, p[item], w[item], cur_weight);

        else

        {

            int item_percent = (int) ((1 + (float) cur_weight / w[item]) * 100);

            printf("Added %d%% (%d Rs., %dKg) of object %d in the bag.\n", item_percent, p[item], w[item], item + 1);

            total_profit -= p[item];

            total_profit += (1 + (float)cur_weight / w[item]) * p[item];

        }

    }

    printf("Filled the bag with objects worth %.2f Rs.\n", total_profit);

}

Practice Questions:

Example 2: Example 1: Find the optimal solution for knapsack problem for n=7 and m=16

Example 3: Example 1: Find the optimal solution for knapsack problem for n=3 and m=20.

Example 3: Example 1: Find the optimal solution for knapsack problem for n=4 and m=60.

📌Friends this is the end of post I hope you all understand the knapsack problem using greedy approach. We will meet in next post with new application of greedy approach till continue reading...