Before we officially begin, I'd like to say a few digressions:
I know the greedy algorithm is a bit difficult for many students. The difficult thing is not to understand the concept, but to do it at first sight, then give up once you do it, and then give up halfway.
I want to say this is normal, because the greedy algorithm is an algorithm idea, but there is no routine to talk about, unlike the last time we studied binary trees, the problem solving was recursive+iterative, which can be integrated from top to bottom, from bottom to top and from left to right, and the routine is obvious.
Needless to say, when it comes to dynamic programming, it is easier to distinguish greedy algorithm from dynamic programming.
What should I do if I encounter these problems? Just do it, just do it+summary.
greedy algorithm
To learn the greedy algorithm, we must first learn its concept.
Greedy algorithm refers to the optimal or optimal (most favorable) choice in each step from the initial state of the problem, and the optimal value (or better value) of the result is obtained.
Through this concept, we can know two key points of greedy algorithm:
Greedy algorithm always makes the best choice when solving problems.
The result of greedy algorithm is not necessarily the optimal result, but it is definitely close to the optimal solution.
It seems that these two points may be difficult to understand. I use two examples to understand.
Example 1: We now have four kinds of coins, namely 20, 1 0,5,1. How many coins do I need to make up 36 yuan?
According to the greedy algorithm, we definitely need some twenties to come up. This problem needs 1, leaving 36-20 = 16.
After watching 20, let's look at 10 yuan. We need 10 block 10 yuan, and now we have 16- 10 = 6.
Next, look at 5 and 1, which need 1 respectively.
In the end, we got the answer that if we want to accept 36 yuan, we need at least four bills.
In this example, the largest banknote is used for matching every time, and the remaining balance is matched with the smaller denomination. This is what we said at 1. When solving problems, we always make the best choice at present.
Example 2: Let's take coins scattered as an example. Now we have three kinds of coins: 1 0,9 and1. How many coins do we need at least to collect 18 yuan?
In this example, if we still use the above greedy strategy, it will be over.
When I came up, I saw that I needed 10 yuan, so this question needed 1 and the remaining amount was 8 yuan, so I couldn't use 9 bets, only 8 bets of 1 yuan, so the final result was that I used 9 bets.
And through elementary school knowledge, we can see with the naked eye that it is ok to use two 9 yuan banknotes.
This example illustrates the second point: the result obtained by greedy algorithm is not necessarily the optimal knot.
See if this is stupid? Stupid is right.
Now you should remember that the greedy algorithm is only useful in some cases. As for what is part of the situation, it depends on doing more questions.
Hey, hey, don't start work first, then look, for example, the above two examples, you have to look at the law between numbers. In example 1, coins are multiples of each other, but in example 2, there is no regularity.
This must be done by doing more questions and summarizing more.
When to use greed?
To be honest, this is where the greedy algorithm is "difficult" for us, that is, nothing to model directly tells us "this is greed."
If you insist, most of them are used in combinatorial optimization problems like the examples given in the previous section, and the process of solving involves multi-step judgment.
When you encounter such a problem, your idea can rely on the greedy algorithm, but it is only "OK".
Because you see such a problem, when you think of a greedy algorithm, you must first come up with a greedy strategy yourself, and then you have to verify whether the results produced by the greedy strategy you use are optimal. If not, you may need to use dynamic programming that we will learn in the next project.
You will probably ask how to verify it, and just give a few reliable examples to verify it.
Of course, when I say "reliable" here, it's just some special cases. Otherwise, if you give a few random examples and find that they are all right, you will feel that what you are doing is right at this time, and it may just be that these examples you gave are just right.
I want to say a few more words here:
In fact, generally speaking, the most reliable way to verify the correctness of greedy algorithm like this is through mathematical deduction, such as mathematical induction and reverse method.
But what can I say? Although the mathematical deduction is correct and the result is correct, it is completely unnecessary for us, not to mention that many people can't deduce it at all. Even if they do, it doesn't mean much to us. After all, the purpose is different, so we will go far.
From our point of view, we can completely verify most problems by quoting some special cases.
Of course, if you want to ask me how to give a special case, I can only tell you: just do more questions.
Greedy method solving steps.
The steps of greedy algorithm are actually very similar to divide-and-conquer algorithm.
When I talked about the divide-and-conquer algorithm before, I talked about the three steps of the divide-and-conquer algorithm:
Points: divide the original problem into smaller sub-problems, which are independent of each other and have the same form as the original problem.
Conquer and recursively solve the sub-problems after partition.
Combination: This step is not necessary. Some problems involve merging the solutions of subproblems, and merging the solutions of subproblems into the solutions of original problems. Some problems are not needed, just find the solution of the sub-problem.
The steps of the greedy algorithm are similar. If you are sure that the greedy algorithm is solvable, there are three steps:
(1) decomposes the problem into multiple subproblems.
(2) Choose the appropriate greedy strategy to get the local optimal solution of each sub-problem.
(3) Merge the local optimal solution of the subproblem into the optimal solution of the original problem.
Do you think it's easy? Gnome male-",when you do the problem, you will know that sometimes what you see is not the real feeling.
So much for the greedy algorithm. There are really not many things in theory. I just give you an impression after reading it.
As long as you know something theoretically, you have no choice but to study greed. Just do more questions and practice, and you will feel it if you watch more.
In fact, a series of actions are: Er, this problem seems greedy. Try it and get a result. Find some special cases to test it. It is the optimal solution. Everything is fine, but it is not the optimal solution. Then think about whether it can be solved by dynamic programming or something.
Finally, there is no need to panic about the greedy algorithm. Take a step back, even if you don't learn well, the problem is not big. In general, there are fewer people who are greedy for exams in interviews.