The basic idea of greedy algorithm
1. Establish a mathematical model to describe the problem.
2. Divide the solved problems into several sub-problems.
3. Solve each sub-problem and obtain the local optimal solution to the sub-problem.
4. Synthesize the local optimal solution of the sub-problem into a solution to the original solution of the problem.
The process of implementing this algorithm:
Starting from a certain initial solution to the problem;
While can move forward to a given overall goal
Find a solution element of the feasible solution;
A feasible solution to the problem is composed of all solution elements.
Greedy Selective Nature
The so-called greedy selection nature means that the overall optimal solution of the problem you are looking for can be achieved through a series of local optimal choices. In other words, when considering which choice to make, we only consider the best choice for the current problem without considering it. The result of the subproblem. This is the first basic element of the feasibility of greedy algorithms.
Greedy algorithms make iteratively greedy choices, and each time a greedy choice is made, the problem you are looking for is reduced to a smaller sub-problem.
For a specific problem, to determine whether it has a greedy choice nature, it is necessary to prove that the greedy choice made at each step ultimately leads to the overall optimal solution to the problem.
2. Optimal substructure properties <br />When the optimal solution of a problem contains the optimal solution of its sub-problem, this problem is said to have the optimal sub-structural properties. The optimal substructure nature of the problem is a key feature that can be solved by greedy algorithms.
The general process of greed
The code copy is as follows:
Greedy(C) //C is the input set of the problem, that is, the candidate set
{
S={ }; //The initial solution set is an empty set
while (not solution(S)) // Set S does not constitute a solution to the problem
{
x=select(C); //Make greedy choices in candidate set C
if feasible(S, x) //Judge whether the solution after adding x to the set S is feasible
S=S+{x};
C=C-{x};
}
return S;
Problem description:
Currently, there are coins with face values of 2 jiao 5 cents, 1 jiao 5 cents, 5 cents and 1 cents. Please give the best solution to find n cents (requiring the minimum number of coins to be found)
Problem analysis:
According to common sense, when we go to the store to buy things and find money, the boss always gives us the maximum denomination first. If it is not enough, look for a smaller denomination until it is full. If the boss asks you for scores or a few cents, you will definitely not do it. In addition, he may not have so much fragmented money for you. In fact, this is a typical problem of greedy choice.
Algorithm design and implementation of the problem :
Let me give you an example first. If the boss wants to ask me for 99 cents, he has the above coins with a face value of 25, 10, 5, and 1. In order to find me the minimum number of coins, should he look for it like this? , first look at how many 25 points should be found, oh 99/25=3, it seems to be 3. If there are 4, we have to give the boss another 1 point. If I don't do it, then the boss can only give me I got 3 25 points and I was given 24 less, so I had to give me 2 10 points and 4 1 points.
The code copy is as follows:
//Arithmetic for finding change
//Input: array m, store the number of face values arranged from large to small in sequence. n is the number of money to be found, all units are divided into points
//Output: array num, compare the number of coins with different denomination values in array m, and find a money plan
public static int[] zhaoqian(int m[],int n)
{
int k=m.length;
int[] num=new int[k];
for(int i=0;i<k;i++)
{
num<i>=n/m<i>;
n=n%m<i>;
}
return num;
}
The code copy is as follows:
public class zhaoqian
{
public static void main(String[] args)
{
int m[]={25,10,5,1};
int n=99;
int[] num=new int[m.length];
num=zhaoqian(m,n);
System.out.println(n+" money-finding plan: ");
for(int i=0;i<m.length;i++)
System.out.println(num<i>+"zip"+m<i>+"face value");
}
public static int[] zhaoqian(int m[],int n)
{
int k=m.length;
int[] num=new int[k];
for(int i=0;i<k;i++)
{
num<i>=n/m<i>;
n=n%m<i>;
}
return num;
}
}
The above is all the content of this article, I hope you can like it.