• Greedy Algorithms 101
  • By Mario Osorio
  • The Nuggets translation Project
  • Permanent link to this article: github.com/xitu/gold-m…
  • Translator: chaingangway
  • Proofreader: PingHGao, sun tu

Greedy algorithm, did you get the hang of it?

Greedy algorithm is easy to implement in most cases, and it is also one of the most commonly used coding routines when solving optimal problems, and its resource consumption is relatively low.

However, this algorithm also has disadvantages, it can not guarantee to find the optimal solution every time, sometimes can only find the solution close to the optimal solution. Anyway, in many cases, close to the optimal solution is enough.

This algorithm generally iterates “n” times over a problem of “n” size, so its complexity may be O(n), O(n × log(n)), but no more than O(n²).

Most of the problems solved by this algorithm have two characteristics:

  1. Greedy property: This means that the local optimal solution is adopted for each iteration, regardless of the global impact. We believe that by constantly solving local optima we will eventually get global optima, but as I said before, that’s not necessarily true. To prove that the optimal solution is found in each iteration, we need to use induction (obviously not a simple proof).
  2. Optimal substructures: I mentioned some of them earlier. The problem to be solved must be divided into subproblems, each of which has an optimal solution.

In this article, we’ll learn how to write our own greedy algorithm and then use it to solve a very famous problem.

Greedy Algorithms Generic Template (Java)

public ArrayList greedy(ArrayList candidates) {
    solution;
    while(! isSolution(solution) && (candidatesLeft(candidates)) { cadidate = selectCandidate(candidates); removeCandidate(candidate, candidates);if(isGoodCandidate(candidate, solution)) { addCandidate(candidate, solution); }}if (isSolution(solution)) {
            return solution;
        } else {
            return null; }}}Copy the code

Before EXPLAINING the code, LET me give you some definitions of the terms used in pseudocode.

  1. Candidates: All possible solution sets. It can be any data type, but is usually iterable. We’ll understand this better as we work through the sample problem. Now please remember the conclusion 😁.
  2. Candidate: In the solution set, one of our currently selected solutions.
  3. Solution: The first instance of a Solution variable is simply a data structure where we will store the current Solution.
  4. isSolution, candidatesLeft, removeCandidate, addCandidate, isGoodCandidate: These are also the methods we will create, some of which need not be complete for some practical problems, but I will define them all as methods to summarize the code template.

First, we initialize the data structure, which can be arrays, Booleans, integers… We just need to make a statement.

solution
Copy the code

Then, let’s look at the while loop, which has two methods in its loop condition. These methods must be written, but sometimes a full method body is not required, such as this one to determine whether there are any alternative solutions left.

while(! isSolution(solution) && (candidatesLeft(candidates))Copy the code

When we find that we have not yet found a solution and that there are alternatives left to try, we will select an alternative solution and immediately remove it from our alternative solution set.

cadidate = selectCandidate(candidates);
removeCandidate(candidate, candidates);
Copy the code

The next step is simple. If the candidate solution is the correct solution, it is simply added to the solution structure.

if (isGoodCandidate(candidate, solution)) { 
    addCandidate(candidate, solution); 
}
Copy the code

We then simply check to see if the problem has reached a solved state and return the solution.

if (isSolution(solution)) { 
    return solution; 
} else { 
    return null; 
}
Copy the code

Now that we’ve looked at the code and explained it roughly, I’m going to give you a problem to try and solve for yourself. This is a well-known question and the answer is easy to find on the Internet, but I suggest you try to solve it yourself.

Change problems

There are six types of coins, each with a value of {50,20,10,5,2,1}, which are passed as parameters in descending order. Each coin could be our alternative solution. You must find the best way to exchange it. (Use the fewest coins for change)

Example input: 15 (we must make up 15 with the minimum number of coins and return the coin collection)

Example output: 10, 5 (we return the set of coins with sums of 15 and the smallest number of coins)

In the deterministic coin system {50,20,10,5,2,1}, the algorithm can find the optimal solution, but please note that if the candidate solution changes, the algorithm may not find the optimal solution.

prompt

If you haven’t tried hard enough, you shouldn’t be watching 🤨… Just kidding, go ahead, I’m sure I hope you’ve learned something new 😄.

  • In the selectCandidate() method, you first select the coin with the largest denomination, and then fill the remaining change with smaller coins. During this process, you should always check to see if there is any excess change.

solution

The solution I provide is written in Java and uses object-oriented knowledge.

public class Coin {
    private int value;
    private int quantity;
    Moneda(int value, int quantity) {
        this.value = value;
        this.quantity = quantity;
    }
    /* getters & setters */
}

/* This is actually the "hard" part */
int selectCandidate(ArrayList < Integer > values) {
    int biggest = Integer.MIN_VALUE;
    for (Integer coin: values)
        if ((biggest < coin)) biggest = coin;
    return biggest;
}

/* Now the actual schema */

ArrayList < Coin > greedySchema(ArrayList < Integer > values, int quantity) {
    /* We initialize our solution structure */
    ArrayList < Coin > solution = new ArrayList < Coin > ();
    /* Any auxiliary variable is ok */
    int value;
    
    while ((quantity > 0) && (! values.isEmpty())) {/* Select and remove the coin from our monetary system */
        value = selectCandidate(values);
        values.remove(new Integer(value));
        
        /* If this is true, it meanwe can still look for coins to give */
        if ((quantity / value) > 0) {
            solution.add(new Coin(value, quantity / value));
            /* This will lower the quantity we need to give back */quantity = quanity % value; }}/* Once the quantity is 0 we are DONE! * /
    if (quantity == 0) {
        return solution;
    } else return null;
}
Copy the code

resources

If you like how greedy algorithms work and want to dig deeper, visit Hackerrank or Hackerearth, where there are a number of problems to solve that I’m sure you already know a bit about 😊.

Sometimes, I personally use GitHub as a search engine and simply write down the topic I’m looking for [greedy algorithms].

conclusion

To sum up, greedy algorithms can perform well even on simple personal projects that don’t require much time to think about and consume very few resources. Also, many interview questions can be easily solved using greedy algorithms. Most of the time, the memory and complexity requirements can be met using greedy or dynamic programming, but that’s a topic for another day 😉.

Thank you for reading and feel free to comment at 😄.

If you find any mistakes in your translation or other areas that need to be improved, you are welcome to the Nuggets Translation Program to revise and PR your translation, and you can also get the corresponding reward points. The permanent link to this article at the beginning of this article is the MarkDown link to this article on GitHub.

The Nuggets Translation Project is a community that translates quality Internet technical articles from English sharing articles on nuggets. The content covers Android, iOS, front-end, back-end, blockchain, products, design, artificial intelligence and other fields. If you want to see more high-quality translation, please continue to pay attention to the Translation plan of Digging Gold, the official Weibo, Zhihu column.