Analysis of Java greedy algorithm

The basic idea of greedy algorithm

    1. Build a mathematical model to describe the problem.

2. Divide the problem into several sub-problems.

3. Solve each sub-problem and obtain the local optimal solution of the sub-problem.

4. Combine the locally optimal solution of the sub-problem with a solution of the original problem.

The process of realizing the algorithm:

Starting with an initial solution to the problem;

While can further do toward a given overall goal

A solution element of a feasible solution;

All the solution elements are combined to form a feasible solution to the problem.

The nature of greedy choice

          The so-called greedy choice property means that the overall optimal solution of the problem can be obtained through a series of locally optimal choices. In other words, when considering which choice to make, we only consider the best choice for the current problem and do not consider the results of the sub-problem. This is the first fundamental element of greedy algorithms.
The greedy algorithm makes successive greedy choices iteratively, and each greedy choice simplifies the problem to a smaller subproblem.
          For a specific problem, in order to determine whether it has the nature of greedy choice, we must prove that the greedy choice made at each step finally leads to the overall optimal solution of the problem.

2. Optimal substructural properties
            When the optimal solution of a problem contains the optimal solution of its subproblems, the problem is said to have the optimal substructure property. The optimal substructure property of the problem is the key feature that can be solved by greedy algorithm.
The general process of the greedy method

Greedy(C)  //C is the input set of the problem, the candidate set 

{

    S={ };  //The initial solution set is an empty set 

    while (not solution(S))  //The set S does not constitute a solution to the problem 

    {

       x=select(C);    //Make a greedy choice in candidate set C 

       if feasible(S, x)  //To determine whether the solution of set S with x is feasible 

          S=S+{x};

          C=C-{x};

    }

   return S;

Problem description:

Currently, there are quarters, dimes, nickels and nickels in face value. Please give me the best way to give me n cents.

Problem analysis:

As a matter of common sense, when we go to the store for change, the boss always gives us the largest denomination first, and if it's not enough, he'll look for the smaller denomination until it's full. If the boss gives you the score or a few cents, then you certainly do not do, in addition, he may not have so many pieces of money for you to find. This is a classic case of greedy choice.

Algorithm design and implementation of the problem :

First, for example, if the boss to give me 99 cents, he has the face value of the above 25,10,5,1 COINS, respectively, in order to give me the minimum number of COINS, so he should find it, look at how much for a 25 points, showing 99/25 = 3, seem to be three, four, we have to give the boss a 1 minute, I don't do it, so the boss can only give me three 25 points, due to less give me 24, so have to give me two 10 points and four 1 minute.

//Change algorithm 

//Input: array m, which successively stores the par value from large to small, n is the amount of money to be found, and the units are all 

//Output: array num, compare the number of COINS of different denominations stored in the face value of the array m, on the change scheme 

 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;

 }

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+" Of the change scheme: ");

        for(int i=0;i<m.length;i++)

        System.out.println(num<i>+" gold "+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;

 }

}

All the above is the content of this article, I hope you will enjoy it.