“This is the 14th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Five commonly used algorithms (divide and conquer, dynamic programming, greedy, backtracking, branch boundaries (deep and wide priority traversal)), our previous articles have basically covered, except for a greedy algorithm, this article we will walk into the clever use of greedy algorithm.

The basic concept

Greedy algorithm (also known as greedy algorithm), refers to the solution of the problem, always make in the current view is the best choice. In other words, instead of considering global optimality, what he makes is only a local optimal solution in a sense.

Greedy algorithm can not get global optimal solution for all problems, but many problems it can produce global optimal solution or approximate solution of global optimal solution.

Subject characteristics

How can we determine if a problem can be solved with a greedy algorithm?

Because the result obtained by greedy algorithm is not necessarily the global optimal solution, it is difficult to conclude that it can be used by greedy algorithm.

Problems that can be used with greedy algorithms generally have the following characteristics

  • Greedy choice of nature

    The greedy selection property means that the global optimal solution of the problem can be achieved through a series of locally optimal choices, namely greedy selection. This is the first basic element of the feasibility of greedy algorithms and the main difference between greedy algorithms and dynamic programming algorithms.

    Dynamic programming algorithms usually solve each subproblem in a bottom-up manner, while greedy algorithms usually work in a top-down manner, making successive greedy choices in an iterative manner, and reducing the problem to smaller subproblems with each greedy choice.

    For a specific problem, to determine whether it has the property of greedy choice, it must be proved that the greedy choice made in each step leads to the overall optimal solution of the problem.

  • Optimal substructure properties

    When the optimal solution of a problem contains the optimal solution of its subproblems, the problem is said to have the property of optimal substructure.

    The optimal substructure property of the problem is the key feature which can be solved by dynamic programming algorithm or greedy algorithm.

How to choose greedy algorithm and dynamic programming?

Take the backpack problem as an example. Given that we have a backpack with limited capacity, and a number of items of different value and weight, how can we choose to maximize the value of items in our backpack?

This problem is very common in game scenarios, such as the auto-pick up feature, which is sure to pick up the most valuable item for the player.

These questions can also be divided into two types:

  • Part of an item that can be picked up (greedy, prioritized pick up gear can be used)
  • Items are indivisible and can only be picked up or not picked up (greedy is not allowed, this type of problem is also called 0-1 backpack problem)

To solve the train of thought

Generally, greedy algorithms can be used, or dynamic programming can be used to do it. However, considering that dynamic programming is characterized by seeking the optimal solution of the whole, in most of the problems, greedy is lower than dynamic programming in time and space complexity, and easier to achieve.

Whatever the problem, the most important thing for greedy algorithms is to find the most cost-effective solution to the subproblem, that is, the local optimal solution.

Solution process:

  • Divide the problem into subproblems.
  • The local optimal solution of each subproblem is obtained by solving each subproblem.
  • The local optimal solution of the subproblem is synthesized into a solution of the original problem.

For example: the knapsack problem above can be solved by greedy algorithms

Steps:

  • Subproblem: Loading an item
  • Subproblem local optimal solution: load the most cost-effective goods
  • Merge (all loaded item values and)
package com.zhj.interview; import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.stream.Collectors; public class Test10 { public static void main(String[] args) { int capacity = 15; Int [] weights =,1,2,4,12 {1}; Int [] values =,2,2,10,4 {1}; System.out.println(" knapbag Max value: "+ getHighestValue(capacity, weights, values)); } public static double getHighestValue(int capacity, List<Item> itemList = new ArrayList<>(); int[] weights,int[] values){List<Item> itemList = new ArrayList<>(); for(int i=0; i<weights.length; i++){ itemList.add(new Item(weights[i], values[i])); } itemList = itemList.stream().sorted(Comparator.comparing(Item::getRatio).reversed()).collect(Collectors.toList()); Int restCapacity = Capacity; // Double highestValue = 0; For (Item Item: itemList){if(item.weight <= restCapacity){highestValue += item.value; restCapacity -= item.weight; }else{highestValue += (double)restCapacity/(double)item.weight * item.value; break; } } return highestValue; } static class Item { private int weight; private int value; // Private double ratio; public Item (int weight, int value){ this.weight = weight; this.value = value; this.ratio = (double)value / (double)weight; } public double getRatio() { return ratio; }}}Copy the code