This is the sixteenth day of my participation in the August More Text Challenge. For details, see “August More Text Challenge”.

Hi, today we’re going to talk about greedy algorithms, which, like divide and conquer and dynamic programming, is a way of designing algorithms, and you can also think of it as a way of solving problems. Now let’s see what is dynamic programming?

Greedy algorithm

  • Greedy algorithm is a method in algorithm design.

  • It is expected to achieve global optimum through local optimum selection in each stage.

  • The result is not always optimal.

This is just like when I was a child, I didn’t go to school well and played every day. At that time, I was happy, but when I grew up, I couldn’t find a job, and the result was sad. This is the best choice I made at present, but in the overall situation, it is not optimal.

In the process of doing algorithm problems, we can also use the greedy algorithm, but sometimes you get the optimal solution, sometimes you don’t get the optimal solution.

Change change

So let’s do an algorithm problem. It’s called change exchange.

  • Given an array of Coins, which hold change for the corresponding denominars,

  • And an Amount variable, the total amount of money that needs to be exchanged.

  • The result requires the minimum amount of output of the total amount of exchange

At this point, we can use the greedy algorithm to get the local optimal solution, which is to take out the change of 5, take out the change of 5, take out the change of 1, and then get the global optimal solution.

But in the other case, we can’t get the global optimal solution.

If we go through the greedy algorithm, and we get the local optimal solution, we get the four, we get the two ones, and we get the three, that’s not the global optimal solution. I should have taken two 3’s and printed two, which is the globally optimal solution.

So the greedy algorithm is not locally optimal.

Said so much, there is no lack of many greedy algorithm shortcomings, but in some problems, greedy algorithm can be regarded as a good solution, so, learning greedy algorithm, for our learning algorithm, is also a great help.

End~~~