Greedy algorithm of data structure and algorithm

preface

Data structure of the topic has not updated for a long time, and then always want to update a greedy algorithm of the article, so can not drag more, greedy algorithm he came!

define

Greedy algorithms, also known as Greedy algorithms, are defined on Wikipedia.

Greedy Algorithm A Greedy Algorithm is any Algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage.

It can be seen from the above definition that greedy algorithm, like backtracking algorithm and dynamic programming, needs to make a step by step decision. And according to the definition of greedy algorithm, its solution is to choose the best choice (i.e., the local best) in each decision step, hoping to get the global best. But it’s worth thinking about the fact that the local optimal may not be the global optimal, and that’s why it’s different from dynamic programming, where every step is correlated, and you’re looking for the global optimal. According to the definition of greedy algorithm, we also try to program the greedy algorithm:

  1. What is the mathematical model of the problem (variables, steps, goals)
  2. Decompose the problem into subproblems
  3. The local optimal solution of a subproblem
  4. The local optimal solution is deduced to the global optimal solution (of course, the problem of greedy algorithm can be adopted, and the global optimal solution is the real global optimal).

1. Mathematical model of the problem

Abstract the mathematical model, define the meaning of the operational variables, and find out the ultimate goal.

2. Break it down into subproblems

After the model is established, it is important to consider how to carry out step by step operation.

3. Local optimal solution of subproblem

After the partition, how to manipulate variables in each step to get the local optimal solution.

4. Derive global from local

Get the local optimal solution of each step problem, how to deal with the global optimal solution.

5. Simple algorithm template

Greedy() {Create a mathematical model, disassemble the subproblem and find the goalwhile(There are sub-problems to be solved in the next step){obtain the local optimal solution of the sub-problem} integrate the local optimal solution of each step to the global optimal solution according to the goal}Copy the code

According to the above algorithm template, and the process of problem processing, it can be seen that the essence of greedy algorithm is how to get the local optimal solution.

Here are two examples to demonstrate.

Greedy algorithm example

The best time to buy and sell stocks II

The best time to buy and sell stocks II is the force of the selection of more special greedy algorithm of the problem.

Problem description

Power button

122. The best time to buy and sell stocks II

Given an array, the ith element is the ith day price of a given stock.

Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as you can. Note: You cannot participate in more than one trade at a time (you must sell your shares before buying again).

Problem analysis

  1. In this case, if the price of the stock is 0:n-1, the price of the stock is 0:n-1, and the price of the stock is 0:n-1, the price of the stock is 0:n-1, and the price of the stock is 0:n-1, and the price of the stock is 0:n-1, and the price of the stock is 0:n-1. Objective: To maximize my result res after multiple buys and sells.
  2. Break it down into sub-problems: choose one day to buy the stock + choose one day to sell the stock
  3. The locally optimal solution of the subproblem is to buy on day I, if you sell on day I +1 and make a profit, you buy, otherwise you don’t buy. So if you know you made a profit on day I +1 you’re going to buy on day I. And then you go to day I +1 and so on. On the last day, if there are stocks in front of you, you must sell. Otherwise, you do not buy.
  4. The derivation of global optimal from local optimal can be understood as a difference equation, and the difference value of each step is positive, which is local optimal, and a-B + B-c = A-C will not affect the maximum profit result between the lowest buy and the highest sell because of the intermediate buy and sell, so it is feasible.

code

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int n = prices.length;
        for (int i = 1; i < n; ++i) {
            ans += Math.max(0, prices[i] - prices[i - 1]);
        }
        returnans; }}Copy the code

Lemonade change

Lemonade change is relatively simple and easy to think about the greedy algorithm problem, you can try to analyze the problem of greed according to this problem.

Problem description

Power button

Customers line up to buy your products, one cup at a time (in the order they pay their bills).

Each customer buys a glass of lemonade and pays you $5, $10 or $20. You have to give the correct change to each customer, which means the net transaction is $5 per customer.

Notice that you don’t have any change to start with. Return true if you give the correct change to each customer, false otherwise.

Problem analysis

So this is a very simple problem, typical greedy algorithm. When you want change for a fifteen-dollar bill, you give ten dollars first in ten-dollar bills, then in five-dollar bills; If you don’t have a $10, give me three $5 bills. Give a $5 bill when you need change. Return false if there is no change.

code

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int fiveNums = 0;
        int tenNums = 0;
        for (int bill : bills) {
            if (bill == 5) {
                fiveNums++;
            } else if (bill == 10) {
                if (fiveNums == 0) {
                    return false;
                }
                fiveNums--;
                tenNums++;
            } else {
                if (fiveNums > 0 && tenNums > 0) {
                    fiveNums--;
                    tenNums--;
                } else if (fiveNums >= 0) {
                    fiveNums -= 3;
                } else {
                    return false; }}}return true; }}Copy the code

conclusion

The greedy algorithm is the end of the preliminary explanation, first to find out whether the greedy algorithm is feasible, and then try to make a greedy strategy. Of course, the greedy algorithm is not omnipotent, when some of the relevance does not need to consider the previous state of the problem, you can consider whether the greedy algorithm. In the process of application, you can ask yourself the following questions:

  1. What is the local optimum?
  2. What is the global best?
  3. Can the local best reach the global best?

Greedy algorithm is also a step strategy algorithm. In the learning process, greedy algorithm, backtracking algorithm and dynamic programming can be studied and understood together.