This article has participated in 「 New people's creation ceremony 」 Activities , Start the road of nuggets creation together .
Statement ： The copyright belongs to me , Offenders will investigate .
Please quote source for reprint https://juejin.cn/post/7111942157082034212
1.1. Greedy Algorithm
1.1.1. Algorithm definition
Greedy Algorithm （ Also known as greedy algorithm ） Refer to , In solving the problem , Always make what seems to be the best choice at the moment . in other words , Greedy algorithm is not considered from the overall optimization , The algorithm obtains the local optimal solution in a sense , Near global optimal solution .
1.1.2. The basic idea
The basic idea of greedy algorithm is , Disassemble a large problem into several sub problems , Make the best choice for each subproblem , Finally, the outputs of all subproblems are combined to obtain the optimal solution of the large problem . The design steps are ：
（1） Build a mathematical model to describe the problem .
（2） Divide the problem into several sub problems .
（3） Each subproblem is solved , Get the local optimal solution of the subproblem .
（4） Synthesize the local optimal solution of the subproblem into a solution of the original solution .
Greedy algorithm can not get the overall optimal solution for all problems , The key is the choice of greedy strategy , The chosen greedy strategy must have no aftereffect , That is, the previous process of a certain state will not affect the later state , Only related to the current state .
Take financial management as an example , Financial management has two attributes of risk and income , We hope to find the best way to manage money , If we are greedy for low risk , When looking for financial products , We can sort by risk , Pick the product with the lowest risk ; If we are greedy for high profits , It can be sorted by rate of return , Pick the product with the highest yield ; If we want both low risk and high return , The risk and return rate of each financial product can be quantified , Rank the ratio of risk to return , Select the most cost-effective financial products . The above can be seen as three different greedy strategies .**
1.1.3. Code implementation -- Change for money
Problem description ：
There is a denomination of 1 element 、5 element 、10 element 、20 element 、50 element 、100 Yuan notes , Now hope to pay N element , At least how many banknotes are needed ？
Algorithm analysis ：
The purpose of the problem is to find out the minimum number of banknotes needed . The problem can be decomposed into several sub problems , Sort notes by denomination , Find out how many pieces you need at least 100 Of paper money 、 How many 50 Of paper money 、 How many 20 Paper money, etc ; Divide the total amount by 100, The integer obtained is the least required 100 The number of banknotes , The remainder is used as input for subsequent calculations , Iteratively calculate the minimum number of notes required for each denomination ; The number of notes of each denomination adds up , Make up the final optimal solution , That is, the minimum number of notes required .
Code implementation ：
【 example 1-1】 Change for money ：
papers = [100, 50, 20, 10, 5, 1] # Banknote amount sorted by size
total_money = 248 # The amount to be paid
temp = total_money # The remaining change
total_count = 0 # Total number of notes
for paper in papers:
if temp >= paper:
least_count = temp // paper # Locally optimal solution , The minimum number of notes required for each type of note
total_count += least_count
print(" Local calculation ： Minimum need {} Zhang {} element ".format(least_count, paper))
temp = temp % paper
if temp == 0:
break
print(" Final calculation ： Minimum need {} Paper money ".format(total_count))
Execution results :
Local calculation ： Minimum need 2 Zhang 100 element
Local calculation ： Minimum need 2 Zhang 20 element
Local calculation ： Minimum need 1 Zhang 5 element
Local calculation ： Minimum need 3 Zhang 1 element
Final calculation ： Minimum need 8 Paper money
