Since the beginning of the public account, I have been thinking about how to do a good job in the training of the algorithm, because The sea students in this aspect of the algorithm is really not enough. Therefore, I now want to make a “365 algorithm daily learning plan”.
The main objectives of the Scheme:
1. In this way, I want to supervise my harder learning algorithm.
2. I want to “group” with my friends to learn and communicate the dribs and drabs of learning algorithm. “
Main contents of the Plan:
1. Consolidate basic knowledge of data structure and algorithm.
2. Progressive OJ algorithm training. Schedule of “plan” : Every Wednesday and Saturday the article is a bit long, I hope I can read it patiently.
— Said in the front
“Algorithms of the Day” Project 01 Punching in:
Problem description
Given a positive integer N, what is the maximum common multiple of any three numbers chosen from 1 to N? Input format
Enter a positive integer N. Output format Prints an integer representing the least common multiple you found. Example Input 9 Example Output 504 Data scale and conventions
1 <= N <= 106.
Solution and implementation
The following idea is given by the partners of “Algorithm Daily Learning Exchange Community”. Thank you for your support and attention.
Analysis of ideas:
The maximum and minimum common multiple is associated with the maximum and minimum common multiple of two numbers, that is, the product of two numbers (note: two consecutive natural numbers are mutually exclusive).
Again, we can think about the last three numbers.
1. If n is odd, n, n-1, and n-2 are even and odd. There is only one even factor in n, so there is no factor of 2. There is no factor of 3 between these three numbers.
2. If n is even, then n, n-1, and n-2 are even, even, even, and then n, n-2 must contain a factor of 2, so it is not worth dividing by 2. So if you think about replacing n minus 2 with n minus 3, and making it even and odd, there’s also a question,
N and n-3, if n%3==0, then it’s even less worthwhile to divide by 3. I’m going to change the even number n to n minus 2, and I’m going to change it to n minus 1, n minus 2, n minus 3, and 1. So it is.
So based on the above analysis, we can write the following code:
1import java.util.Scanner;
2public class Main{
3 public static void main(String[] args) {
4 Scanner scanner = new Scanner(System.in);
5 long n = scanner.nextLong();
6 long result;
7 if(n<3)
8 result=n;
9 else{10if(n%2! =0) 11 result=n*(n-1)*(n-2); 12else if(n%3! =0) 13 result=n*(n-1)*(n-3); 14else15 result=(n-1)*(n-2)*(n-3); 16 } 17 System.out.println(result); 18}} 19Copy the codeIn fact, the above algorithm is the greedy idea, which goes something like this:
Start with the largest three numbers. If the largest numbers are odd, then there are two odd numbers in the three adjacent numbers. The largest common divisor is 1, and the least common multiple is n(n-1)(n-2). If it’s even, then if we move back, if we think about n(n-1)(n-3), then the difference between n and n-3 is 3, the only way that this is going to work is if n is not divisible by 3, otherwise it’s going to be (n-1)(n-2)(n-3).
This topic because of the use of the idea of greed, so the following to introduce the greedy algorithm.
Greedy algorithm
I. Basic Concepts:
A greedy algorithm is one that, when solving a problem, always makes what seems to be the best choice at the moment. In other words, instead of considering global optimality, what he makes is only a local optimal solution in a sense.
Greedy algorithm has no fixed algorithm frame, the key of algorithm design is the choice of greedy strategy. It must be noted that the greedy algorithm can not get the overall optimal solution for all problems, and the greedy strategy selected must have no aftereffect, that is, the process after a state does not affect the previous state, but is only related to the current state.
Therefore, the greedy strategy used must be carefully analyzed to see if it meets the no-aftereffect.
Two, the basic idea of greedy algorithm:
1. Build a mathematical model to describe the problem. 2. Divide the problem into subproblems. 3. Solve each subproblem to obtain the local optimal solution of the subproblem. 4. Synthesize the locally optimal solution of the subproblem into a solution of the original problem.
Three, greedy algorithm is applicable to the problem
Greedy strategy is applicable to the premise that local optimal strategy can lead to global optimal solution.
In practice, greedy algorithms are rarely applicable. Generally, to determine whether a problem analysis is suitable for greedy algorithm, we can first select several actual data under the problem to analyze, then we can make a judgment.
Fourth, the implementation framework of greedy algorithm
1. Start from an initial solution of the problem; 2while(can make further progress towards a given general goal) 3 {4 Using feasible decisions, find a solution element of feasible solutions; 5} 6 Form a feasible solution of the problem by combining all solution elements;Copy the codeFive, the choice of greedy strategy
Because greedy algorithm can only solve the local optimal solution strategy to achieve the global optimal solution, therefore, we must pay attention to judge whether the problem is suitable for using greedy algorithm strategy, whether the solution is necessarily the optimal solution of the problem.
6. Sample analysis
Here’s a problem that you can try out with a greedy algorithm, and the greedy solution is good, but it’s not optimal.
There is a backpack. The capacity of the backpack is M=150. There are 7 items and items can be divided into any size. It is required that the total value of items in the backpack be the maximum, but not exceed the total capacity. Item A B C D E F G Weight 35 30 60 50 40 10 25 Value 10 40 30 50 35 40 30
Analysis: Objective function: ∑ PI maximum constraint condition is that the total weight of the loaded items does not exceed the backpack capacity: ∑ WI <=M(M=150) (1) According to the greedy strategy, choose the most valuable items to load into the backpack, the result is optimal? (2) Can the optimal solution be obtained by loading the items with the minimum weight each time? (3) Choose the item with the largest value per unit weight each time, which becomes the strategy to solve the problem.
It is worth noting that the greedy algorithm is not completely impossible to use, once the greedy strategy proved to be established, it is a kind of efficient algorithm. Greedy algorithm is one of the most common algorithms because it is simple and easy to construct greedy strategy is not very difficult.
Unfortunately, it has to be proven before it can actually be applied to the algorithm.
In general, the proof of greedy algorithms revolves around: the optimal solution of the whole problem must be derived from the optimal solution of the subproblems that exist in the greedy strategy. As for the three greedy strategies mentioned in the example, none of them is tenable (and cannot be proved), they are explained as follows:
(1) Greedy strategy: Choose the one with the most value. Example:
W=30 Items: A, B, C Weight: 28, 12, 12 Value: 30, 20, 20
According to the strategy, item A should be selected first, and then no more can be selected. However, item B and C are better.
(2) Greedy strategy: select the least weight. Its counterexample is similar to the counterexample of the first strategy. (3) Greedy strategy: choose the item with the largest value per unit weight. Example:
W=30 Items: A, B and C Weight: 28 20 10 Value: 28 20 10
According to the strategy, the three items have the same value per unit weight, so the program cannot make A judgment based on the existing strategy. If A is selected, the answer is wrong.
Example ② [evenly divided cards] there are N piles of cards, numbered 1,2… , n. There are several cards in each pile, but the total number of cards must be a multiple of n. You can take a bunch of cards on any pile and move them. The rules for moving cards are as follows: a card taken from number 1 can only be moved to number 2; Cards taken from the numbered heap n can only be moved to the numbered heap n-1; Cards taken from other piles can be moved to adjacent piles to the left or right. Now I want to figure out a way to make the same number of moves on each pile in the least number of moves. For example: n=4, 4 piles of cards are: ① 9 ② 8 ③ 17 ④ 6 Move three times to achieve the purpose: take four cards from ③ and put them on ④, then three cards from ③ to ② and then one card from ② to ①.
Input/Output Example: 4
9 August 17 June
Screen display: 3
Algorithm analysis: let a[I] be the number of cards in the ith pile (0<=I<=n), v be the number of cards in each pile after evenly divided, and S be the minimum number of moves.
We’re using a greedy algorithm to move the cards from left to right. If the number of cards in heap I is not equal to the average, then move once (that is, s plus 1) and move in two ways:
1. If a[I]>v, move a[I]-v sheet from heap I to heap I+1; 2. If a[I]<v, move v-a[I] sheets from heap I+1 to heap I.
For the sake of design, we think of the two cases as moving a[I]-v from heap I to heap I+1, with a[I]= V; a[I+1]=a[I+1]+a[i]-v.
It is possible to remove cards from the I+1 pile and replenish the I+1 pile with cards that are less than zero.
If n=3, the number assigned to the three stacks is 1, 2, 27, and v=10, in order to make the first stack 10, you have to move 9 from the second stack to the first stack, and only 2 from the second stack, does that mean that the greedy method was wrong?
We continue to analyze the process of moving CARDS according to rule, from the second pile over the tickets to the first pile of 9, after the first pile has 10, the second pile the remaining 7, from the third pile move 17 to the second reactor, just three of the CARDS is ten, the result is right, we are in the process of moving, just change the order of the mobile, the mobile number of inconvenience, so this problem using greedy method is feasible.
Java source code
1public class Greedy {
2 public static void main(String[] args) {
3 int n = 0, avg = 0, s = 0;
4 Scanner scanner = new Scanner(System.in);
5 ArrayList<Integer> array = new ArrayList<Integer>();
6 System.out.println("Please input the number of heaps:");
7 n = scanner.nextInt();
8 System.out.println("Please input heap number:");
9 for(int i = 0; i < n; i++) { 10 array.add(scanner.nextInt()); 11} 12for (int i = 0; i < array.size(); i++) {
13 avg += array.get(i);
14 }
15 avg = avg / array.size();
16 System.out.println(array.size());
17 System.out.println(avg);
18 for (int i = 0; i < array.size() - 1; i++) {
19 s++;
20 array.set(i + 1, array.get(i + 1) + array.get(i) - avg);
21 }
22 System.out.println("s:"+ s); 23}} 24Copy the codeTo solve problems using greedy algorithms, two problems need to be solved:
One is whether the problem is suitable to be solved by greedy method. Let’s look at an example of currency finding. If a currency system has three denominations, the face value of which is one dime, five cents and one cent, the greedy method can be used to find the minimum number of coins. If these three currencies are changed to one dime, five cents and one cent, the greedy method cannot be used to solve the problem. Greedy method is very convenient to solve problems, but its scope of application is very small. There is no general method to judge whether a problem is suitable for solving by greedy method. In informatics competition, it is necessary to judge by personal experience.
The second is how to choose a greedy criterion to ensure the optimal solution of the problem after determining the greedy algorithm. When choosing the greed standard, we should verify the chosen greed standard before using it. We should not be confused by the seemingly correct greed standard, as shown in the following example.
Let n positive integers join them into a row to form the largest multi-bit integer.
For example, if n is 3, three integers are 13,312,343, and the largest integer is 34331213.
Another example: when n=4, the four integers 7,13,4,246, the largest integer is 7424613.
Input: n N Number Output: multiple digits connected
Algorithm analysis: this problem is easy to think of the use of greedy method, in the test when many students in the order of integers from large to small connected, the test examples are also consistent, but the final test results are not all right. By this standard, it is easy to find a counterexample: 12,121 should make up 12,121, not 12, 112, so does it make up from small to large when they include each other? Not necessarily. If 12,123 is 12, 12, 12 instead of 12,123, there are a lot of different situations. Is this problem can not be greedy method?
If a+b>=b+a, put a before B, and if b+ B >=b+a, put a before B, and vice versa.
Java source code
1public static void main(String[] args) {
2 String str = "";
3 ArrayList<String> array = new ArrayList<String>();
4 Scanner in = new Scanner(System.in);
5 System.out.println("Please input the number of data:");
6 int n = in.nextInt();
7 System.out.println("Please input the data:");
8 while(n-- > 0) { 9 array.add(in.next()); 10} 11for (int i = 0; i < array.size(); i++)
12 for (int j = i + 1; j < array.size(); j++) {
13 if((array.get(i) + array.get(j)).compareTo(array.get(j) + array.get(i)) < 0) { 14 String temp = array.get(i); 15 array.set(i, array.get(j)); 16 array.set(j, temp); 17} 18} 19for (int i = 0; i < array.size(); i++) {
20 str += array.get(i);
21 }
22 System.out.println("str=:"+ str); 23}} 24Copy the codeThe selection made by the greedy algorithm can depend on the selection made in the past, but it never depends on the selection made in the future, and it does not depend on the solution of the subproblem, so the greedy algorithm has a certain speed advantage compared with other algorithms. If a problem can be solved in several ways at once, greedy algorithms should be one of the best choices.
This is greedy of a few ideas and basic application, if still have what problem, can leave a message or private letter I!
The resources
- https://blog.csdn.net/a925907195/article/details/41314549
Phase to recommend
- Java Language Interview Questions (2)
- “365 Algorithm Daily Learning Plan” : 02 Clocking – Linear table (the first preview of book gift activity)
- Concurrency Basics part 1: Introduction to threads
