This is the 7th day of my participation in the August Text Challenge.More challenges in August

This article uses simple examples to understand the greedy algorithm, and does not use particularly difficult questions. It only uses the greedy algorithm separately. The greedy algorithm will be explained in detail by examples in the follow-up

Meaning: Greedy strategy, also known as greedy strategy each step takes the best choice in the current state (local optimal solution), thus hoping to derive the global optimal solution

Greedy applications:

Huffman tree

Minimum spanning tree algorithm: Prim, Kruskal

Shortest path algorithm: Dijkstra

Optimal Loading problem (Pirates of the Caribbean)

Topic:

In the southeast of North America, there is a mysterious sea, is the most active pirates of the Caribbean One day, pirates captured a cargo ship full of various antiques, each antique is very valuable, once broken will lose its value

How can the pirates load as many antiques as possible onto the pirate ship, which has a deadweight of W and a weight of 𝑤 I per piece?

For example, W is 30, and 𝑤 I is 3, 5, 4, 10, 7, 14, 2, 11

Greedy strategy: Prioritize the smallest antiques every time

① Choose an antique with a weight of 2 and a remaining weight of 28

② Choose an antique with a weight of 3 and a remaining weight of 25

③ Choose an antique with a weight of 4 and a remaining weight of 21

④ Choose the antique with the weight of 5 and the remaining weight of 16

⑤ Choose an antique with a weight of 7 and leave a weight of 9

Can carry up to 5 antiques

public static void main(String[] args) { int[] weights = {3, 5, 4, 10, 7, 14, 2, 11}; Arrays.sort(weights); int capacity = 30, weight = 0, count = 0; for (int i = 0; i < weights.length && weight < capacity; i++) { int newWeight = weight + weights[i]; if (newWeight <= capacity) { weight = newWeight; count++; System.out.println(weights[i]); }} system.out.println (" count "+" count "); }Copy the code

Change change

Topic:

Suppose there are 25 cents, 10 cents, 5 cents, 1 cent coins, now want to give the customer 41 cents change, how to minimize the number of coins?

Greedy strategy: Choose the coin with the largest denomination first and foremost each time

① Choose a 25-cent coin and leave 16 cents

② Choose a ten-cent coin and leave six cents

③ Choose a five-cent coin and leave one cent

④ Choose a one-cent coin

The final solution is a total of four coins a quarter, a ten, a five, and a one

Public static void main(String[] args) {int[] a={25,5,10,1}; Arrays.sort(a); int money=50; int coins=0; for(int i=a.length-1; i>=0; i--){ if(money<a[i]){ continue; } money-=a[i]; i++; coins++; } System.out.println(coins); }Copy the code

Another way to change change

Topic:

Suppose there are 25 cents, 20 cents, 5 cents, 1 cent coins, now want to give the customer 41 cents change, how to minimize the number of coins?

Greedy strategy: Choose the coin with the largest face value first at each step

① Choose a 25-cent coin and leave 16 cents

② Choose a 5-cent coin and leave 11 cents

③ Choose the five-cent coin and leave six cents

④ Choose a five-cent coin and leave one cent

⑤ Choose a 1-cent coin

The final solution is one quarter, three fives, and one one, making a total of five coins

In fact, the optimal solution for this problem is: two 20-cent coins, one one-cent coin, a total of three coins

Pay attention to

Greedy strategies do not always lead to global optimal solutions

Because not all possible solutions are tested, it is easy to make early decisions, so the optimal solution cannot be achieved

Greedy for immediate local benefit maximization, can not see the long-term future, go step by step advantages: simple, efficient, do not need to exhaust all possibilities, usually used as the auxiliary algorithm of other algorithms

Disadvantages: short-sighted, do not consider other possibilities from the whole, take the local optimal solution every time, will not go back, so rarely get the optimal solution

In fact, most of our problems with greedy algorithms are not just greedy algorithms, most of them are matched with dynamic arrays to solve problems

0-1 knapsack

Question:

There are n items and a backpack with a maximum load capacity of W. Each item weighs 𝑤 I and is worth 𝑣 I

What items can be packed into the backpack to maximize the total value of the backpack without the total weight exceeding W?

Note: there are only 1 items per item, which means that you can only choose 0 or 1 items per item, hence the 0-1 backpack problem

If greedy strategy is adopted, there are three options

(1) Value dominance: prioritize the items with the highest value to put into the backpack

(2) Weight: the lightest items should be put into the backpack

③ Value density dominant: the items with the highest value density should be put into the backpack (value density = value ÷ weight).

Because we’re not doing this directly in LeetCode, we need to implement an entity class before we do this

Example:

Public class Article {public int weight; public int value; public double valueDensity; public Article(int weight, int value) { this.weight = weight; this.value = value; ValueDensity = value * 1.0 / weight; } @Override public String toString() { return "Article [weight=" + weight + ", value=" + value + ", valueDensity=" + valueDensity + "]"; Public class Knapsack {public static void main(String[] args) {select(" value ", (Article a1, Article a1) Article a2) -> { return a2.value - a1.value; }); Select (" weight ", (Article a1, Article a2) -> {return a1. Weight - a2. Weight; }); Select (Article a1, Article A2) -> {return Double.compare(a2. ValueDensity, a1. ValueDensity); }); } static void select(String title, Comparator<Article> cmp) { Article[] articles = new Article[] { new Article(35, 10), new Article(30, 40), new Article(60, 30), new Article(50, 50), new Article(40, 35), new Article(10, 40), new Article(25, 30) }; Arrays.sort(articles, cmp); int capacity = 150, weight = 0, value = 0; List<Article> selectedArticles = new LinkedList<>(); for (int i = 0; i < articles.length && weight < capacity; i++) { int newWeight = weight + articles[i].weight; if (newWeight <= capacity) { weight = newWeight; value += articles[i].value; selectedArticles.add(articles[i]); }} system.out.println (" [" + title + "] "); System.out.println(" total value: "+ value); for (int i = 0; i < selectedArticles.size(); i++) { System.out.println(selectedArticles.get(i)); } System.out.println("-----------------------------"); }}Copy the code

This code can be copied and pasted to the compiler, and then debug to understand the code running process

Have a question can be left a message, the blogger read the reply