Shulou(Shulou.com)06/02 Report--

This article to share with you is about greedy algorithm is what, Xiaobian think quite practical, so share to everyone to learn, I hope you can read this article after some harvest, not much to say, follow Xiaobian to see it.

1 concept

Greed means choosing the outcome that is most beneficial to oneself every time when making choices, so as to ensure the maximization of one's own interests. Greedy algorithm is to use this greedy thinking and get an algorithm.

Greedy algorithm as one of the five algorithms, in the data structure is widely used. For example, in the Prim algorithm for minimum spanning tree, the vertex selected is an endpoint of the edge with the smallest weight among the candidate edges. In the Kruskal algorithm, the edge with the least weight is selected to join the set each time. In the process of constructing Huffman tree, the node with minimum weight is selected to construct binary tree every time. This situation of always choosing the current optimal solution every time the subproblem is solved is exactly in line with the meaning of greed.

Greedy algorithm can be simply described as: big things small, small things. For a larger problem, divide the complex problem into smaller problems by finding overlaps with subproblems. And for each sub-problem solution to choose, find the optimal value, processing, and then find the optimal value, and then processing. That is to say, greedy algorithm is an algorithm that takes the best or optimal choice in the current state in each step of selection, so as to get the best or optimal result.

Greedy algorithm always makes the best choice at present when solving the problem. In other words, without considering the global optimality, what is done is only a local optimal solution in a sense. Greedy algorithm can not produce global optimal solution for all problems, but it can produce global optimal solution or approximate solution for many problems with wide range.

2 algorithm flow

  (1) Establish mathematical models to describe the problem.

  (2) Divide the problem into several subproblems.

  (3) Solve each subproblem and obtain the local optimal solution of the subproblem.

  (4) Combine the local optimal solution of the subproblem into a solution of the original problem.

3 Pseudocode starts from an initial solution of the problem

while (able to move one step towards a given overall goal)

do

selecting the current optimal solution as a solution element of the feasible solution;

A feasible solution of the problem is formed by combining all solution elements.

4 Example Title Description:

Xiao Ming has five denominations of banknotes in his hand: 1, 5, 10, 50 and 100. The corresponding number of banknotes for each type is 5, 2, 2, 3 and 5 respectively. If Xiao Ming had to pay 456 yuan, how many notes would he need?

topic analysis

1) Establishment of mathematical models

  Let Xiaoming choose the denomination of banknotes Xi each time, the number of banknotes needed is n, and the remaining amount to be paid is V, then there are:

X1 + X2 + … + Xn = 456.

(2) Split the problem into sub-problems

  The process of Xiaoming selecting banknotes for payment can be divided into n sub-problems: that is, each sub-problem corresponds to:

Select one of the remaining banknotes if 456 is not exceeded.

(3) Develop greedy strategies to solve subproblems

The greedy strategy is to select the largest denomination paper money under the allowable conditions. Then the whole solution process is as follows:

Select a banknote with a face value of 100, then X1 = 100, V = 456 - 100 = 356;

Continue to select the banknote with the face value of 100, then X2 = 100, V = 356 - 100 = 256;

Continue to select banknotes with a face value of 100, then X3 = 100, V = 256 - 100 = 156;

Continue to select banknotes with a face value of 100, then X4 = 100, V = 156 - 100 = 56;

Select a banknote with a face value of 50, then X5 = 50, V = 56 - 50 = 6;

Select a banknote with a face value of 5, then X6 = 5, V = 6 - 5 = 1;

Select a banknote with a face value of 1, then X7 = 1, V = 1 - 1 = 0; end of solution

(4) Combine all solution elements into the solution of the original problem

The number of banknotes Xiaoming needs to pay is 7, including 4 with a face value of 100 yuan, 1 with a face value of 50 yuan, 1 with a face value of 5 yuan and 1 with a face value of 1 yuan.

code implementation const int N = 5;

int Count[N] = {5,2,2,3,5};//Number of notes per note

int Value[N] = {1,5,10,50,100};

int solve(int money) {

int num = 0;

for(int i = N-1;i>=0;i--) {

int c = min(money/Value[i],Count[i]);

money = money-c*Value[i];

num += c;//Total number of sheets

}

if(money>0) num=-1;

return num;

}

The above is what greedy algorithm is, Xiaobian believes that some knowledge points may be what we see or use in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.