Programmer Algorithm Basics - Greedy Algorithm

Preface

Greed is an inherent ability of human beings, and greedy algorithm is a general term for overall planning based on greedy decision-making.

[[231562]]

For example, a common algorithm written test question - Jump:

• There are n boxes in a row, each box has a number a[i] on it, which means that at most a[i] boxes can be jumped to the right;
• Xiao Ming is standing at the first box on the left. Can he reach the box on the far right?
• For example: [1, 2, 3, 0, 4] can reach the 5th box;
• [3, 2, 1, 0, 4] cannot reach the 5th box;

We can naturally come up with a solution: jump to the right as far as possible to see if we can reach it in the end.

This article is an introduction to this greedy decision making.

text

Basic concepts of greedy algorithm

In a narrow sense, greedy algorithm refers to a special method for solving optimization problems. In the solution process, the best choice is always made at the moment. Because of the characteristics of optimal substructure, the local optimal solution can get the global optimal solution. This greedy algorithm is a special case of dynamic programming. Problems that can be solved by greedy can also be solved by dynamic programming.

In a broad sense, greedy refers to a general greedy strategy that makes greedy decisions based on the current situation. Take the question of Jump Jump as an example:

• We found that the core of the problem lies in the maximum distance that can be reached to the right, which we represent as maxRight;

At this time, there is a greedy strategy: start from the first box and traverse to the right, and for each box passed, continuously update the value of maxRight.

The thinking process of the greedy algorithm

The greedy thinking process is similar to dynamic programming, which still consists of two steps: making big things small and small things nothing.

Make a big deal small:

A larger problem, by finding overlaps with sub-problems, divide the complex problem into multiple small problems;

It's trivial:

Find the core of decision-making from small problems and determine a strategy to get the optimal solution, such as the farthest distance that can be reached to the right in "jump";

Mathematical proofs are often used to prove whether a local optimal solution can lead to a global optimal solution.

Specific application of greedy algorithm

1. Issues with banknote change

There are a[1], a[2], a[3], a[4] pieces of 1 yuan, 2 yuan, 5 yuan, and 10 yuan banknotes respectively. How many pieces of banknotes are needed to make m yuan?

If it is dynamic programming:

• To collect m yuan, we must first collect m-1, m-2, m-5, and m-10 yuan. We use dp[i] to represent the minimum number of banknotes required to collect i yuan.
• There is dp[i]=min(dp[i-1], dp[i-2], dp[i-5], dp[i-10]) + 1;
• It is easy to know that dp[1]=dp[2]=dp[5]=dp[10]=1;

Based on the above recursive equation and initialization information, all values ​​of dp[1~m] can be easily derived.

Something seems wrong? Is it so complicated to make change normally?

From the perspective of the greedy algorithm, when m>10 and we have a 10 yuan banknote, we give priority to the 10 yuan banknote, and then the 5 yuan, 2 yuan, and 1 yuan banknotes.

• We know from daily experience that this is the right thing to do, but why?
• If we change the question to this, will the original strategy still work?
• There are a[1], a[2], and a[3] 1 yuan, 5 yuan, and 7 yuan banknotes respectively. How many banknotes are needed to make m yuan?

Next, let's analyze this strategy:

• It is known that for m yuan banknotes, a, b, c pieces of 1, 2, and 5 yuan banknotes are used, so we have a+2b+5c=m;

Suppose there is a situation where the number of 1, 2, and 5 yuan banknotes used is x, y, and z. The number of 5 yuan banknotes used is less (z

We set k = 5*(cz), k yuan banknotes require floor(k/2) 2 yuan banknotes, k%2 1 yuan banknotes; (because if there are 2 1 yuan banknotes, you can use 1 2 yuan banknote to replace it, so the 1 yuan banknote can only be 0 or 1)

It is easy to know that to reduce (cz) 5 yuan banknotes, we need to increase floor(5*(cz)/2) 2 yuan banknotes and (5*(cz))%2 banknotes, which makes x+y+z necessarily greater than a+b+c.

From this we know that there can be no better solution using fewer 5-yuan notes.

So giving priority to large-denomination banknotes is a correct greedy choice.

For 1, 5, and 7 yuan notes, for example, to make up 10 yuan, if 7 yuan notes are used first, the number of notes is 4; (1+1+1+7)

But if only 5 yuan notes are used, the number of notes is 2; (5+5)

In this case, giving priority to large-denomination banknotes is an incorrect greedy choice. (But dynamic programming can still get the optimal solution)

2. Server task scheduling issues

The server has n tasks to execute. Each task has a start time of Si seconds and an end time of Ti seconds. Only one task can be executed at the same time.

How to arrange tasks so that as many tasks as possible can be completed within time m?

If it is dynamic programming:

The number of tasks completed in the first i seconds can be inferred from the number of tasks completed in the previous 1 to i-1 seconds.

• We use dp[i] to represent the number of tasks that can be completed in the first i seconds;

When calculating the number of tasks that can be completed in the first i seconds, we have two decisions for the jth task:

1. If this task is not performed, dp[i] will not change;
2. To perform this task, we must free up (Sj, Tj) time, so dp[i] = max(dp[i], dp[ S[j] ] ) + 1;

For example, if task j starts at the 5th second and ends at the 10th second, if i>=10, then dp[i]=max(dp[i], dp[5] + 1); (equivalent to allocating the time from the 5th second to the i-th second to task j)

Considering the greedy strategy again, how do people arrange this kind of multi-tasking in real life? Let me describe it in another way:

• Xiao Ming works part-time at school. He works 10 hours a day.
• Now there are multiple part-time positions, each with a start and end time, and Xiao Ming can only do one part-time job at the same time;

How many part-time jobs can Xiao Ming do every day?

We naturally think of a strategy: do the part-time job that ends early first!

Why?

Because if you finish this job first, you will have more time to do other part-time jobs.

We are born with this ability to optimize our decisions.

3. Candy sharing problem

After n children finished playing the game, the teacher was going to give them candies;

Each person has a score a[i]. If the score is higher than that of the person on his left and right, then he will get more candies than the person on his left and right, and each child will get at least one candy.

Ask the teacher how many candies we need to prepare at least.

This is a LeetCode question.

This problem cannot be solved directly using dynamic programming, for example, using dp[i] to represent the minimum number of candies required by the first i people.

Because the state (the minimum number of candies for the first i people) indicates that it will be affected by the i+1th person. If a[i]>a[i+1], then the i-th person should have more candies than the i+1th person.

That is, this state means that there is no aftereffect.

If we were to distribute the candies, how would we distribute them?

The answer is: start with the lowest score.

Sort by scores, starting from the lowest, and each time determine whether the scores are higher than the scores on the left and right.

Assume that each person gets c[i] candies, then for the i-th person, c[i]=max(c[i-1],c[c+1])+1; (c[i] defaults to 0. If c[i-1] is 0 when calculating i, it means that i-1 has a higher score than i)

However, the time complexity of this solution is O(NLogN), and the main bottleneck is sorting.

If you submit, you will get a prompt that Time Limit Exceeded.

We need to optimize the greedy strategy:

• Let’s look at the left and right situations separately.

If we only consider the case where the score is higher than that of the person on the left, it is easy to get the strategy:

• Traversing from left to right, if a[i]>a[i-1], then c[i]=c[i-1]+1; otherwise c[i]=1.

If we consider the person who has a higher score than the person on the right, we need to start from the rightmost side of the array and traverse to the left:

• If a[i]>a[i+1], then c[i]=c[i+1]+1; otherwise c[i] remains unchanged;

After two traversals, we can get an allocation plan with a time complexity of O(N).

4. The problem of a small boat crossing a river

n people want to cross a river, but there is only one boat; the boat can only carry two people at a time, and each person has a crossing time a[i] to take the boat alone. If two people (x and y) take the boat together, then the crossing time is the larger value of a[x] and a[y].

What is the shortest time required to get everyone across the river?

The question gives key information: 1. It takes a long time for two people to cross the river;

There is also hidden information: 2. After two people cross the river, one person needs to drive the boat back;

To ensure that the total time is as short as possible, there are two key principles: the time difference between the two people should be as small as possible (to reduce waste), and the time it takes for the boat to return should also be as short as possible (to reduce waiting).

Let’s not consider the case where an empty ship returns. If there are an infinite number of ships, how should they be allocated?

Answer: Each time, choose the person who takes the longest time from the remaining people, and then choose the person whose time is closest to his.

Consider the case of only one boat, assuming there are three people A/B/C, and it takes A

Then the fastest solution is: A+B goes, A returns; A+C goes; the total time is A+B+C. (Because A is the fastest, letting others go back and forth will only take longer, the principle of reducing waiting)

If there are four people A/B/C/D, and it takes A

• The fastest way to send someone back and forth is A+B going, A coming back, A+C going, A coming back, A+D going; the total time is B+C+D+2A (principle of reducing waiting)
• The fastest and second fastest way to send people together is: A+B goes first, A returns; C+D goes, B returns; A+B goes; the total time is 3B+D+A (principle of reducing waste)

Comparing the choices of options 1 and 2, we found that the difference is only in A+C and 2B;

Why is there no D in the difference between options 1 and 2?

Because D must cross the river eventually, and the time it takes must be D.

If there are 5 people A/B/C/D/E and it takes A

Still looking at it from the slowest E. (Refer to our infinite number of ships)

• Plan 1, reduce waiting time; send E first, and then consider the situation of four people;
• Plan 2, reduce waste; send E/D first, then consider the situation of A/B/C; (Plan 2 for 4 people)

By the time we had 5 people, we had already clearly discovered a feature: the questions were repetitive and could be solved by sub-questions.

According to the situation of 5 people, we can deduce the state transition equation dp[i] = min(dp[i - 1] + a[i] + a[1], dp[i - 2] + a[2] + a[1] + a[i] + a[2]);

Based on the situations of 1, 2, 3, and 4 people we considered, we can calculate the initialization value of dp[i] respectively:

 dp[1] = a[1];  
 dp[2] = a[2];  
 dp[3] = a[2]+a[1]+a[3];  
 dp[4] = min (dp[3] + a[4] + a[1], dp[2]+a[2]+a[1]+a[4]+a[2]);

From the above state transition equation and initialization value, we can deduce the value of dp[n].

This is a combination of greedy and dynamic programming. The greedy strategy is used in the decision-making process of dynamic programming.

Summarize

The greedy learning process is to optimize your own thinking.

It is to grasp the existing information and make the best decision.

Here are some collected greedy exercises for practice.