A Complete Guide to Solve Knapsack Problem Using Greedy Method

Knapsack Problem

 

The knapsack problem is one of the famous and important problems that come under the greedy method. 

 

As this problem is solved using a greedy method, this problem is one of the optimization problems, more precisely a combinatorial optimization. 

 

The optimization problem needs to find an optimal solution and hence no exhaustive search approach could be applied to it.

 

The Knapsack problem is used in logistics, mathematics, cryptography, computer science, and more. 

 

The knapsack examples help in real-world such as resource allocation problems.

 

Knapsack Problem With Example

 

A knapsack can also be considered as a bag and the problem is to fill the bag with the objects in such a way that the profit is maximized. As we are trying to maximize the profit, this problem is optimization as well as maximization problem.

 

Every optimization problem has some sort of constraint associated with it, what is the constraint here? 

 

The constraint is to fill the objects such that the weight of the objects doesn’t exceed the capacity of a bag. The weight of the objects should be less than or equal to the capacity of the bag.

---

---

Consider a bag that has a capacity of 12 kg, let's take the maximum capacity of a bag as ‘m’,  here m = 12. Now let us take objects, object weights, and profit associated with that weight.

---

Example of the knapsack problem

---

We can see in the above example that there are 4 objects and in the example, we can also see the profit and weights of the object. We can see that the total weight of the objects is exceeding the capacity of the bag( total weight: 6 + 2 + 7 + 5 = 20).

 

Now, what should be our approach to fill the bag? We can either choose the object with a maximum profit or maximum weight, let’s try out both approaches.

 

(Read blog: What Does Probabilistic Programming Work?)

 

1. Selecting the solution with respect to the maximum profit

 

If we select maximum objects with the maximum profit to fill the bag, then the solution will be-:

 

Object with maximum profit = 4th object

Profit associated with 4th object = 15

The weight associated with the 4th object = 5

Therefore, if we load this object to the bag we are left with = 12-5 = 7

---

---

The next object with maximum profit is the 3rd object, where the profit is ‘14’ and the weight is ‘7’. After loading this object to the bag, the capacity of the bag remains-:

---

---

Now, the bag is completely full and we cannot add any more objects to the bag, we shall calculate the profit-:

 

15 + 14 = 29

 

Now, let us calculate the profit while selecting the solutions on the basis of minimum weight.

 

2. Selecting the solution with respect to the minimum weight

 

The first object with the minimum weight = 2nd object

The weight associated with 3rd object = 2

Profit associated with 3rd object = 5

 

Therefore, after loading this object to the bag, the remaining bag capacity is-:

---

---

The second object with the minimum weight is the 4th object with weight ‘5’.The profit associated with this object is ‘15’. After loading this object, the bag is left with-:

---

---

Now the capacity of the bag is 5kg but the next minimum weight is ‘6’, therefore we will take 5 out of that 6 and the profit will be calculated accordingly. When we load this object into the bag, our bag would be completely filled.

 

Now, the bag is completely filled, let us see the profit in this case-:

 

Total profit= 5 + 15 + ⅚ 12 = 30

 

If you look at this example, you might think that our second approach is good and will provide us with optimal results every time, but it is not. Both approaches do not guarantee the optimal solution. Therefore, we will calculate the profit/weight ratio to find the optimal solution.

 

We will calculate the profit/weight value for each object and then we will include the solution from decreasing order of p/w ratio. Let us take the below example with the bag capacity of 12.

---

Example with the bag capacity of 12

---

p/w of the first object -: 12/6= 2

p/w of the second object -: 5/2= 2.5

p/w of the third object -: 14/7= 2

p/w of the fourth object -: 15/5= 3

 

The maximum profit/weight ratio is of the fourth object, therefore we will load it in the bag. Similarly, we will load the objects in decreasing p/w ratio and we will get the following results-:

 

Weight of the 4th object = 5

Profit of the fourth object = 15

Remaining capacity of the bag -> 12-5 = 7

 

Weight of the 2nd object = 2

Profit of the second object= 5

Remaining capacity of the bag -> 7-2 = 5

 

The weight of the 1st object is 6 but we only have a capacity of 5, therefore we will only use 5 out of 6 weights from this object and the profit will also be distributed similarly.

 

Profit of the first object-> ⅚ 12= 10

Remaining capacity of the bag-> 5-5 = 0

 

Total profit = 15 + 5 + 10 = 30

 

Therefore, 30 is an optimal solution for this particular problem. The power by weight ratio method helps in finding the optimal solution for the optimization problem.

 

(Suggested blog: Linear Search And Binary Search Using Python)

 

Pseudo Code and Time Complexity of Knapsack Problem

 

Let us understand the working of knapsack with the help of a plain description of the code-:

 

for i in range(1,n):

    calculate p/w



    Sort objects in descending order of p/w ratio



    if M>0 and wi<=M:

        M = M-wi

        P = p + pi



    else:

        p = p + pi(M/wi)

 

In the above pseudo-code, M is the maximum capacity of the bag whereas wi is the weight of the objects. 

 

Let us try to decode the complexity of the knapsack algorithm step by step-:

 

We begin with a for loop starting from the first object to the last object and the complexity of the for loop is nothing but o(n), now the next step is an important step, we have to sort the objects in descending order of power/weight ratio. 

 

We can use several sorting algorithms like the bubble sort, merge sort, quick sort, and more. 

 

Let us say that we used merge sort for sorting as it is one of the fastest sorting algorithms, then the complexity of merge sort is o(nlogn). Lastly, we have used the if statement, and the complexity of that if statement is 0(n).

 

Now, as the maximum complexity in our analysis is o(nlogn), therefore the complexity of the knapsack algorithm is 0(nlogn).

 

 

Conclusion

 

In this blog, we learned about the knapsack problem and how it can be solved using a greedy method. 

 

We have used several examples and approaches to find the best way to find the optimal solution to a knapsack problem. But is the greedy method the only way to solve the knapsack problem? 

 

No, the knapsack problem can also be solved using dynamic programming also but the only problem with dynamic programming is that it does not ensure the optimal solution to the problem and hence, the greedy method is the best suitable method to solve the knapsack problem. 

 

In the later section of the blog, we have learned about the complexity of the knapsack problem and the pseudo-code for the knapsack algorithm.