Greedy algorithm (English: greedy algorithm), also known as greedy algorithm, is an algorithm that takes the best or optimal (i.e. the most favorable) choice in the current state in each step of selection, hoping to lead to the best or optimal result. Take a simple example, that is, change. For example, you need to give customers 85 yuan in cash. In order to minimize the amount of money, you should choose a face note of no more than 85, 50 yuan, then 20 yuan, then 10 yuan, and finally 5 yuan. This is the simplest example of greedy algorithm.
  this is top-down, and the corresponding dynamic programming is bottom-up.

  methods: 1. Create a mathematical model to describe the problem.
  2 divide the problem into several subproblems.
   3 solve each subproblem to obtain the local optimal solution of the subproblem.
   4 synthesize the local optimal solution of the subproblem into a solution of the original solution problem.

//Greedy algorithm general algorithm
Greedy(C){
	S={};
	while(not solve(S)){
		x=select(C);
		if feasible(S,x){
			S=S+{x};
			C=C-{x};
		}
	}
	return S;
}

   classic Title Description 1: [fatmouse's trade]: fathouse has m puonds cat food. He wants to exchange food with the cat. The cat takes care of n warehouses. He doesn't see j[i]pounds food in the warehouse. He needs f[i]pounds cat food. He doesn't need to exchange all the food in the warehouse. j[i] * a% = f[i] * a%. Ask how much food fathouse can exchange at most.

  analysis: the classic greedy algorithm uses the structure to sort according to the exchange rate, and then runs the array again. For a simple example, for example, m=5,n=3, when 7, 2, 4, 3, 5, 2 are input; 13.333 will be output. Reason: first select the group with no more than m, then select the group with the most, select 7, then 5, and then there is one remaining M. at this time, enter the second group, then 4 / 3 * 1 = 1.333, a total of 13.33. Therefore, the algorithm sorts J[I]/F[I] of each group, and each group has a cost performance ratio.

#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;

struct inp{
    double x,y;//x represents j[i],y represents f[i]
    double c;//c stands for j[i]/f[i], sorted by ratio
}node[1005];

bool cmp(inp a,inp b){
    return a.c>b.c;
}

int main(){
    int i,n,m;
    double j;
    while(cin>>m>>n&&n!=-1&&m!=-1){
        for(i=0;i<n;i++){
            cin>>node[i].x>>node[i].y;
            node[i].c=node[i].x/node[i].y;
        }
        sort(node,node+n,cmp);
        j=0;
        for(i=0;i<n;i++) {
            if (node[i].y <= m) {
                j += node[i].x;
                m -= node[i].y;
            } else {
                j += m * node[i].c;
                break;
            }
        }
        printf("%.3f",j);
    }
    return 0;
}

   classic topic 2: [this summer vacation is not AC hdu2037] "this summer vacation is not AC?" "yes." "what are you doing?" "watch the world cup, fool!" "@#$% ^ & *%..." indeed, the world cup is coming, and the fans' festivals are coming. It is estimated that many acmers will abandon their computers and run to TV. As a fan, you must want to watch as many complete games as possible. Of course, as a good young man in the new era, you will also watch some other programs, such as news network (never forget to care about national affairs), very 6 + 7, super girl, and Wang Xiaoya's happy dictionary. Suppose you already know the broadcasting schedule of all the TV programs you like to watch, Will you make reasonable arrangements? (the goal is to watch as many complete programs as possible)
Input
   the input data contains multiple test instances. The first line of each test instance has only one integer n (n < = 100), indicating the total number of programs you like to watch, and then n lines of data, each line includes two data ti_ s,Ti_ E (1 < = i < = n) represents the start and end time of the ith program respectively. In order to simplify the problem, each time is represented by a positive integer. n=0 indicates the end of input and no processing.

Output
  for each test instance, output the number of TV programs that can be seen completely, and the output of each test instance accounts for one line.

  analysis: such questions belong to time series problems, such as the following table

  Begin[i] and End[i] indicate the end. In fact, it is to find the longest sequence to meet Begin[i] < end [J] <... Begin [M] < end [n]. Therefore, to solve the above problems, we only need to sort the end time, which belongs to the conventional greedy algorithm.

#include <iostream>
#include <algorithm>
using namespace  std;

struct inp{
    int Begin;
    int End;
}node[100];

bool cmp(inp a,inp b){
    return a.End<b.End;
}

int main(){
    int n,i,count,j;
    while(cin>>n&&n){
        count=1,j=0;
        for(i=0;i<n;i++){
            cin>>node[i].Begin>>node[i].End;
        }
        sort(node,node+n,cmp);
        for(i=1;i<n;i++){
            if(node[j].End<=node[i].Begin){
                count++;
                j=i;
            }
        }
        cout<<count<<endl;
    }
    return 0;
}

  classic title 3: there is a pile of sticks. The length and weight of each stick are known in advance. The wooden sticks should be processed one by one by woodworking machines. It takes some time for the machine to prepare the bar, which is called the set time. The setting time is related to cleaning operations and changing tools and shapes in the machine. The setting time of the woodworking machine is as follows: (a) the setting time of the first stick is 1 minute. (b) If l < = L 'and W < = w', the machine will not need the preparation time for the stick with length L 'and weight W' after just processing the stick with length L 'and weight W'. Otherwise, it will take 1 minute to set.
  you will find the minimum setting time to process the given n sticks. For example, if you have five sticks whose length and weight pairs are (4,9), (5,2), (2,1), (3,5), and (1,4), the minimum setting time should be 2 minutes, because there are a series of pairs (1,4), (3,5), (4,9), (2,1), (5,2).
input
  the input consists of t test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of two lines: the first line has an integer n, 1 < = n < = 5000, indicating the number of wooden rods in the test case, and the second line contains N 2 positive integers l1,w1,l2,w2,..., ln, wn, each with a maximum amplitude of 10000, where li and wi are the length and weight of the ith wooden rod respectively. 2n integers separated by one or more spaces.
output
   the output shall include the minimum setting time in minutes, one per line.

Analysis: This is a classic area coverage problem.

#include <iostream>
#include <algorithm>

using namespace std;

struct lip{
    int l,w;
}node[5000];

bool cmp(lip a,lip b){
    return a.l<b.l||(a.l==b.l&&a.w<b.w);
}

int main(){
    int n,i,count,t;
    while(cin>>t){
        while(t--){
            while(cin>>n){
                for(i=0;i<n;i++){
                    cin>>node[i].l>>node[i].w;
                }
                sort(node,node+n,cmp);
                count=1;
                for(i=1;i<n-1;i++){
                    if(node[i].l>node[i+1].l||node[i].w>node[i+1].w){
                        count++;
                    }
                }
                cout<<count;
            }
        }
    }
    return 0;
}

   the above is part of the exercise. More training is needed for the greedy algorithm. In fact, through these questions, we can clearly see the advantages of the greedy algorithm. We should sort the preprocessed data. Of course, before that, we should establish a structure to store and record multiple groups of data for comparative price comparison. However, the greedy algorithm has its shortcomings after all. Before using this algorithm, it needs to be able to prove (or obviously) that it can be used. This algorithm is similar to finding the optimal data in the remaining conditions, and even if it is not satisfied later, it cannot be returned for processing (difference and divide and conquer, dynamic planning).
  there will be some exercises on greedy algorithms in the future. Of course, more algorithms are in progress.