Greedy algorithms for beginners algorithms

“This is the 12th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Greedy algorithm

Greedy algorithms, also known as greedy algorithms, have a simple principle: when solving a problem, always make the best choice for the moment.

Let’s take a look at an example.

Course arrangement table

Suppose you have the following class schedule, and you want as many classes as possible in one room.

You can’t fit them all in one room because some classes have conflicting schedules.

Using greedy algorithms, the solution can be easily arrived at.

• Pick the first class to finish, which is the first class to be taught in this room.
• Next, you have to choose the class that starts after the first class, which is the second class in this room.
• Repeat the process until the selection is complete.

In the end, we arranged a maximum of three courses:

Many said the algorithm was too easy and obvious to take.

But this is the advantage of greedy algorithms, simple, every step to choose the local optimal solution, the final result is the global optimal solution.

However, greedy algorithms do not always get the optimal solution, as in the following example.

Knapsack problem

Assume a backpack can hold 35 pounds of stuff, and pack as many high-value items as possible.

If the greedy algorithm is used, directly install stereo, occupy 30 board space, and then can not fit other items, the final value of 3000 yuan, 5 pounds of space wasted.

But if the computer and guitar are installed, the space is used up, and the final value is 3500 yuan.

Obviously, in the knapsack problem, greedy algorithms can’t get an optimal solution.

But using the greedy algorithm, we get closer to the optimal solution, and a lot of times, we don’t have to get the optimal solution, we get an approximation is enough.

Let’s do another example of taking approximations.

Traveling salesman problem (NP-complete problem)

A tour operator has five cities to visit. What is the shortest trip?

This seemingly simple problem, people to think about a stroke, at most take out a pen and paper to calculate, can think out.

But for computers to solve this problem, the time complexity is order n!

There are 120 different arrangements for 5 cities, 6 is 720,7 is 5040!

It’s a bad algorithm, and it would be better if we used a greedy algorithm.

Choose a city at random, and each time you find a shorter route, go to the nearest city you haven’t visited yet.

It’s not necessarily the shortest, but it’s probably close to the shortest.

Such problems are called NP-complete problems, and some of the smartest people in the world have yet to solve them, only to find approximations.

Scenarios where greedy algorithms apply

Like divide-and-conquer, problems can be broken down into subproblems to be solved.

Divide-and-conquer IN this article, I write algorithms for beginners divide-and-conquer and quicksort (JS) have a detailed introduction.

The optimal solution of the subproblem recurses to the optimal solution of the final problem. The optimal solution of the subproblem is called optimal substructure.

Once a problem can be solved by the greedy method, the greedy method is usually the best way to solve the problem.

Because of the high efficiency of greedy method and its answers are relatively close to the optimal results, greedy method can also be used as an auxiliary algorithm or directly to solve some problems requiring not particularly accurate results.

Greedy algorithms are different from dynamic programming

Greedy algorithms don’t necessarily find the optimal solution, but if you do, you need dynamic programming.

In simple terms, dynamic programming does not necessarily choose the optimal solution for each subproblem, but can store the optimal, suboptimal and desirable solutions.

Once stored, the greedy algorithm cannot be reverted, and each subproblem is solved by choosing the current optimal solution.

Dynamic programming will save the previous results, and select the current according to the previous results, with a rollback function, and finally get a global optimal solution.

When making a choice, dynamic programming will consider several schemes comprehensively and save them. When moving forward step by step, when finding that the previous scheme is not well chosen, it will go back and make some adjustments, and finally adjust to an optimal solution.

Simply put, greedy algorithms are myopic and dynamic programming patterns open up.

Greedy algorithm leetcode first experience

122. The best time to Buy and sell stocks II

Given an array prices, prices[I] represents the price of a stock on the ith day. On each day, you may decide to buy and/or sell shares. You can’t hold more than one share at any time. You can also buy it and sell it on the same day. Return the maximum profit you can make.

Input: prices = [7,1,5,3,6,4] Output: 7 Then, by buying on day 4 (stock price = 3) and selling on day 5 (stock price = 6), the exchange makes a profit = 6-3 = 3.Copy the code

There are many ways to solve this problem, but I’m just going to talk about greedy algorithms.

Local optimal: close when you see good, do not move when you see bad, do not make any long-term plans.

Steps to solve the problem:

1. Create a new variable to count total profits.
2. Iterate through the price array, if the current price is higher than yesterday, buy yesterday, sell today, or don’t trade.
3. At the end of the loop, the sum of all profits is returned

const maxProfit = function (prices) {
  let res = 0
  for (let i = 1, len = prices.length; i < len; ++i) {
    res += Math.max(0, prices[i] - prices[i - 1])
  }
  return res
}
Copy the code

Time complexity: O(n)

Space complexity: O(1)

summary

In life, we can be accused of being short-sighted if we all choose the best option at hand.

But a lot of times, you just pick the best option at a time, and when you accumulate a lot, you can go a long way.

In the algorithm world, greedy algorithm can not necessarily find the optimal solution, but can find the approximate value of the optimal solution relatively simple, if to find the optimal solution to pay a very large cost (NP complete problem), then using greedy algorithm to get an approximate value is good.

Greedy algorithm interview generally not test, but to understand its ideas, or very good, can give us a lot of thinking.

This article introduces the greedy algorithm interview does not test the reason, is a little utilitarian, HHH.

Previous algorithms related articles

The list is introduced

Write a brief introduction to the front-end development algorithm

Tree introduction

Divide-and-conquer and Quicksort (JS) for beginners

Introduction to hash tables

Breadth-first search

Depth-first search