Shulou(Shulou.com)06/02 Report--

This article mainly introduces "how to use Java greedy algorithm". In daily operation, I believe many people have doubts about how to use Java greedy algorithm. The editor consulted all kinds of data and sorted out simple and easy-to-use operation methods. I hope it will be helpful to answer the doubts about "how to use Java greedy algorithm". Next, please follow the editor to study!

What is greedy algorithm

Greedy algorithm means that the best choice of the current stage (or state) is made at each stage, and the result is expected to be the global optimal solution (but not necessarily the global optimal solution).

Greedy algorithm is actually a kind of dynamic programming. Because of its greed, it only focuses on the optimal solution of the current stage, so each sub-problem will only be calculated once. If the global optimal solution can be obtained from this, compared with dynamic programming to find the global optimal solution for each sub-problem, its time complexity will undoubtedly be reduced by an order of magnitude.

To give a simple example, for example, given the amount of a certain number (such as 250) and 100, 50, 10, 5, 1 banknotes (unlimited), how can you exchange this amount with the least number of banknotes? obviously, each exchange should start with a large banknote, 100 for the first time, 100 for the second time, 50 yuan for the second time, and less than the maximum denomination of the remaining amount each time. The solution thus obtained must be the global optimal solution! There is no doubt that time complexity is linear.

Let's first look at some examples that can be solved by greedy algorithms.

Example of greedy algorithm

Divide the candy

There are m candies and n children. We are going to give candy to these children now, but there are fewer candies and more children (m).

< n)，所以糖果只能分配给一部分孩子。每个糖果的大小不等，这 m 个糖果的大小分别是s1，s2，s3，……，sm。除此之外，每个孩子对糖果大小的需求也是不一样的，只有糖果的大小大于等于孩子的对糖果大小的需求的时候，孩子才得到满足。假设这 n 个孩子对糖果大小的需求分别是 g1，g2，g3，……，gn。那么如何分配糖果，能尽可能满足最多数量的孩子呢? 求解：这道题如果用贪心来解解题思路还是比较明显的，对于每个小孩的需求 gn，只要给他所有大小大于 gn 的糖果中的最小值即可，这样就能把更大的糖果让给需求更大的小孩。整个代码如下： public class Solution { /** * 获取能分配给小孩且符合条件的最多糖果数 */ private static int dispatchCandy(int[] gList, int[] sList) { Arrays.sort(gList); // 小孩对糖果的需求从小到大排列 Arrays.sort(sList); // 糖果大小从小到大排列 int maximumCandyNum = 0; for (int i = 0; i < gList.length; i++) { for (int j = 0; j < sList.length; j++) { // 选择最接近小孩需求的糖果，以便让更大的糖果满足需求更大的小孩 if (gList[i] a.start)); // 首次遍历从 -1,0 开始 return removeSubDuplicate(-1, 0, intervals); } private static Integer removeSubDuplicate(int pre, int cur, Interval[] intervals) { if (cur == intervals.length) { return 0; } int notRemove = Integer.MAX_VALUE; if (pre == -1 || intervals[pre].end a.start)); int[] dp = new int[intervals.length]; Arrays.fill(dp, 0); dp[0] = 1; // 将 dp[0] 置为 1， 因为就算所有的区间都重叠，则连续不重叠区间到少也为 1 int result = 1; for (int i = 1; i < intervals.length; i ++) { int max = 0; for (int j = 0; j < i; j ++) { if (!isOverlapping(intervals[i], intervals[j])) { max = Math.max(dp[j], max); } } dp[i] = max + 1; } return intervals.length - dp[intervals.length - 1]; } 空间复杂度是多少，由于只有一个 dp 一维数组，所以是 O(n)，时间复杂度呢， 两重循环，所以是 O(n^2)。可以看到和采用递归+备忘录的时间复杂度一样，不过之前其实说了很多次，递归容易导致栈溢出，所以建议还是采用动态规划的方式来求解。 接下来重点来了，来看看如何用贪心算法来求解。首先要把各个区间按照区间的终点从小到大排列，如下

Our idea is the same as the dynamic programming above, first find the maximum number of non-overlapping subintervals, and then use the "total number of intervals-the maximum number of non-overlapping subintervals" as the minimum number of overlapping intervals to be removed.

The steps to find the maximum number of unimportant subregions by greedy algorithm are as follows

Select the interval with the smallest end point and set it to the current interval cur.

Find the next interval that does not overlap with the interval cur by the end of the interval from small to large, and then set this interval to the current interval cur (note that the maximum number of non-overlapping subintervals should be increased by 1), and repeat step 2 until all the intervals are traversed.

The moving picture is as follows. I believe it will be easier for you to understand after reading the moving picture.

If you know how to understand the problem, it's easy to write the code.

/ * greedy algorithm to solve * / private static Integer removeSubDuplicateWithGreedy (Interval [] intervals) {/ / sort the end points of the interval from small to large Arrays.sort (intervals, Comparator.comparingInt (a-> a.end)); int cur = 0; / / set the first to the current interval int count = 1; / / the maximum number of non-overlapping intervals, the minimum is 1 for (int I = 1) I < intervals.length; ifold +) {/ / non-overlapping if (intervals [cur]. End < intervals [I] .start) {cur = I; count++;}} / / the total number of intervals minus the maximum number of non-overlapping intervals, that is, the minimum removed overlap interval return intervals.length-count;}

What is the time complexity? there is only one cycle, so it is O (n), which is indeed an order of magnitude faster than the O (n ^ 2) of dynamic programming. A simple analysis of why the greedy algorithm is so fast, as you can see from the above code, it only cares about the immediate optimal solution (select the next interval that does not overlap with the current interval and then iterate through it in turn, and then you no longer need to care about the previous interval!) As for dynamic programming, we can see from its dp equation (dp [I] = max {dp [j]} + 1) that for each I, we have to traverse the solution from 0 to I from bottom to top to get the maximum value, that is to say, for the subproblem of dynamic programming, because it pursues the global optimal solution, it has a backtracking process (that is, finding the optimal solution of all subproblems from the bottom up). There are some repeated sub-problem calculations in the process of backtracking, and the greedy algorithm does not have this kind of backtracking solution because it pursues the immediate optimal solution, so it saves a lot of operation, so if it can be solved by greedy algorithm, the time complexity can undoubtedly be increased by an order of magnitude.

Greedy algorithm is suitable for scenarios

Let's briefly summarize the greedy algorithm, which means that only the optimal one is selected in each step, and the optimal solution chosen in each step is expected to reach the global optimal solution. To be honest, this is too difficult, because generally the choice of one problem will affect the choice of the next problem, unless the sub-problems are completely independent and unrelated, such as the example of collecting change at the beginning of the article, if the banknotes of a country are weird. There are only three kinds of banknotes, such as 1BI 5J 11. How to make 15 with the least amount of banknotes? if you choose 11 for the first time with greed, then you can only choose 4 1s, that is, 15 = 1 x 11 + 4 x 1. In fact, the optimal solution should be three 5-yuan banknotes, why is greed not applicable in this case? because 11 is chosen for the first time, which affects the choice of banknotes behind, that is to say, the sub-problems are not independent, but restrict each other. Influence each other, so we must pay attention to its applicable scenario when we choose greed.

Let's see if the sum of the shortest path of the triangle can be solved by greedy algorithm.

Looking back at the beginning of the problem, can the shortest path of triangles be solved by greedy algorithm?

Let's review this topic first:

As shown in the figure, the above triangle consists of a series of numbers, which requires the shortest path from vertex 2 to the bottom, only to the two nodes below the current node at a time, such as 3 can go to 6 or 5, not directly to 7.

As shown in the figure: requires the shortest path from node 2 to the bottom, it only cares about nodes 9, 10, the nodes before the number of layers no longer need to care! Because 9 ~ (10) is already the optimal substructure, you can only save the maximum value of each layer of nodes (that is, an one-dimensional array)!

How to solve it with greedy algorithm

1, the first step: go down from 2, because 3 is smaller than 4, so choose 3

Step 2: go down from 3, because 5 is smaller than 6, so choose 5

Step 3: go down from 5. 1 is smaller than 8. Choose 1.

The answer is 11, which is exactly the same as the solution of dynamic programming! Does that mean that this problem can be solved by greedy algorithm?

The answer is no! The reason why the above solution is correct is that these numbers happen to be solved according to greed to get the global optimal solution. If we change the numbers, let's see what happens.

As shown in the figure, if the number is changed to that shown in the figure, the shortest path obtained by greed is 66, while in fact the shortest path should be 16, as shown in the following figure

Why does it not work with greed, because greed pursues the optimal solution in front of each step, once it makes a choice, it will affect the choice of face problems, for example, if you choose 3, you will no longer be able to choose 7! So again, we must pay attention to the greedy application scenario, whether the sub-problems restrict each other and influence each other!

At this point, the study on "how to use the Java greedy algorithm" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.