It’s okay to be greedy here

As kids we were always told how being greedy is never a good idea and in our moral science classes, we read several stories where the greedy person never ended up in an acceptable position and hence, we got the notion how being greedy can take you to a wrong place. But guess what? When it comes to Computer Sciences, being greedy can often lead you to solutions of so many problems. Greedy is not a bad option here but an option that you must take if you want an optimal solution.

And here enters the greedy method. It is an approach to solve problems by taking into consideration the best viable option at the moment. In other words, it tries to find a local optimized solution which may or may not lead to providing globally optimized solutions.

Now the question is when do we know that we can apply this greedy approach to a problem? When a problem satisfies the following properties, you can forget your moral science classes on not being greedy and go ahead and implement your greedy algorithm:

1) Greedy choice property

If one can go ahead and choose the best choice at each step without caring about the choices made at the previous steps. The problem can be solved using greedy approach.

2) Optimal Substructure

If the optimal overall solution to the problem corresponds to the optimal solution to its subproblems, then the problem can be solved using a greedy approach.

The best part of this greedy method is that it is easier to describe and has the capacity to perform better than other algorithms (though not in all cases).

I would take this space and describe one of the applications of the greedy method. We call it the Knapsack Problem. It is an optimization problem where we are constrained to the number of items that can be put in a knapsack which has a limited weight capacity. Given a set of items with specific weights and values, the aim is to get as much value into the knapsack as possible given the weight constraint of the knapsack.

Consider an example where we have the following items with their corresponding weights and values.

Now suppose we have a knapsack where the max capacity is, say five units. Now our goal is to put items in our knapsack such that the profit is maximum.

We can solve it by calculating the value/weight number of each item so that we would know which object has the maximum value corresponding to its weight.

We can see that item C has the most Value/Weight number so we can fill the one unit of our knapsack of with item C. So, we have 4-unit weight remaining in our knapsack. Next, we notice that second highest value/weight number is of item D. So, we can go ahead and pack our knapsack with 4-units of item D in our knapsack. We can see that our knapsack is filled now (1 unit of item C + 4 units of item D). By summing the values of item D and C, we can calculate the highest profit value, i.e., 3+7=10.

Hence, we calculated the highest profitable value we obtained in the knapsack problem. And in conclusion we can understand that there is no problem in being greedy here. (But that does not mean you become greedy in real life. Those moral science classes were given to us for a reason!)

Thank you!