search

Home >Java >javaTutorial >How to use greedy and enumeration in Java

How to use greedy and enumeration in Java

王林
王林forward
2023-05-20 11:46:461120browse

Written test skills: Learn to guess knowledge points based on the data range                                                                                                                                                             # Pen questions).

##n Range Within 20: n Range 200 or less:n Range Within 3000:n Range 1e5 or less: O(n) dual -pointed needle linear DP differential/ prefix and ((√N )

O(n*2^n)

Pressure search /dfs Explosive search

O(n ^3)

##Three-dimensional dp

O(n^2)

two-dimensional dp backpack enumeration two-dimensional prefix and etc.

O(n√n)

 ##Violent search for factors, etc.

n Range 1e6 Within:
O(nlogn)

 The binary answer uses various stl and finds Euler Sieve etc

##n Range 1e7 Within:

# N range within 1e14:

Find the divisor and the number of divisors

Greedy:

Greedy means making the best choice at every step. The problems generally solved have the following characteristics: local optimality can lead to global optimality.

Please note that greed is not a panacea!

There are n items. Each item has a value v[i], and a weight w[i].

Now take items whose total weight does not exceed m. What is the maximum value of the items taken? (Knapsack problem)

  • Strategy 1: Arrange in descending order of value, taking the highest value each time.

  • Strategy 2: Arrange in ascending order of weight, taking the lightest weight each time.

  • Strategy 3: Arrange in descending order according to value/weight (i.e. unit value), and take the one with the highest unit value each time.

Enumeration:

1. Naive enumeration

As the name suggests, use a for loop to enumerate all situations.

2. Status enumeration

Use the properties of n-ary system to enumerate.

Suitable scenario: There are n items in total, each item has m states, enumerating all states of all items, the complexity is O(m^n).

How to write a binary enumeration:

Classic problem: given n numbers a1, a2...an, each number is optional, list all possible solutions. 

for(int i=0;i<1<<n;i++){  //i为1到2^n的状态压缩值   2^n
	int p=i;          //先将i取出
	int sum=0;        //用一个变量维护取出的数之和
	for(j=0;j<n;j++){   //转为二进制进行操作
		sum+=p%2*a[j];    //这句话是求取出来的数之和。p%2为对应二进制位
                  		 //这里也可以进行其他操作，不一一举例。
		p/=2;            //求下一个二进制位
     	}
     //这里可以添加想要的操作。
   }

Algorithm Question 1:

chika and satsuma (use of PriorityQueue Comparator)

Difficulty ⭐⭐

chika likes to eat satsumas very much. Each mandarin orange has a certain degree of acidity and sweetness. Chika likes to eat sweet ones, but not sour ones.

Chika ate k mandarins, and there are n mandarins in total. She will calculate the sum of the sweetness and acidity of the mandarins she ate. chika wants to get the greatest possible sweetness sum. If there are multiple options, she wants the total acidity to be as small as possible.

She wants to know, what is the final total acidity and total sweetness?

Question information: Sort by sweetness in descending order first, then by acidity in ascending order (keep the previous descending order of sweetness first, followed by ascending acidity)

Enter description:

The first line has two positive integers n and k, representing the total number of mandarins and the number of mandarins eaten by Chika respectively. (1≤k≤n≤200000)

The second line has n positive integers ai, representing the acidity of each mandarin orange. (1≤ai≤1e9)

The second line has n positive integers bi, representing the sweetness of each mandarin orange. (1≤bi≤1e9)

Output description:

Two positive integers, separated by spaces. Represent total acidity and total sweetness respectively.

Example

Enter

3 2

1 3 4

2 2 5

Output

5 7

Explanation

Select No. 1 and No. 3 mandarin oranges, the total acidity is 5, and the total sweetness is 7, which is Optimal solution. 

import java.io.*;
import java.util.*;
public class Main{
    public static class Orange{
            int acid;
            int sweet;
            public Orange(int acid, int sweet){
                this.acid = acid;
                this.sweet = sweet;
            }
            public Orange(){}
        }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] tmp = br.readLine().split(" ");
        int n = Integer.parseInt(tmp[0]);
        int k = Integer.parseInt((tmp[1]));
        String[] ai = br.readLine().split(" ");
        String[] bi = br.readLine().split(" ");
        //定义一个优先队列，并根据指定的比较器对其元素进行排序。
        PriorityQueue<Orange> queue = new PriorityQueue<>((Orange o1, Orange o2)->{
            //匿名内部类以lambda的形式定义排序规则
            if(o1.sweet == o2.sweet){
                return o1.acid - o2.acid;
            }else{
                return o2.sweet - o1.sweet;
            }
        });
        for(int i = 0; i < n; i++){
            Orange orange = new Orange();
            orange.acid = Integer.parseInt(ai[i]);
            orange.sweet = Integer.parseInt(bi[i]);
            queue.add(orange);
        }
        long totalAcid = 0;
        long totalSweet = 0;
        for(int i = 0; i < k; i++){
            Orange o = queue.poll();
            totalAcid += o.acid;
            totalSweet += o.sweet;
        }
        System.out.println(totalAcid + " " + totalSweet);
    }
}

Purpose:

Understand what greed is, and you can consider using PriorityQueue Comparator when designing to prioritize.

Algorithm question 2:

you and the sailboat

Difficulty ⭐⭐

Your father is a captain. So you have loved the sea since you were a child. That day, she set off on a sailboat.

There are many treasures on the sea, and the coordinates of each treasure are known. Your initial coordinates are (0,0). She wants to explore two treasures and then return to the starting point.

You want the route to be as short as possible. She wanted to know, what was the length of the shortest route?

Question information: Two for loops enumerate and then save the shortest path.

Input description:

The first line is a positive integer n, representing the number of treasures. (2≤n≤2000)

The next n lines, each line contains 2 positive integers xi and yi, representing the coordinates of the i-th treasure (-3000≤xi,yi≤3000)

There is no guarantee that there will not be two treasures with the same location. Meaning, you can explore both treasures in the same location.

Output description:

The length of the shortest path. Keep 6 digits after the decimal point.

Example

Input

2

1 0

0 1

Output

3.414214

Description

How to use greedy and enumeration in Java##

import java.io.*;
import java.util.*;
 
class Point{
    double x;
    double y;
}
 
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Point[] points = new Point[n];
        for(int i=0;i<n;i++){
            String[] strings = br.readLine().split(" ");
            Point point = new Point();
            point.x = Integer.parseInt(strings[0]);
            point.y = Integer.parseInt(strings[1]);
            points[i] = point;
        }
        double min = Double.MAX_VALUE;//定义最大值，寻找较小值
        //双层遍历枚举
        for (int i=0;i<n-1;i++) {
            for (int j=i+1;j<n;j++) {
                double temp = Math.sqrt(points[i].x*points[i].x + points[i].y*points[i].y) 
                        + Math.sqrt(points[j].x*points[j].x + points[j].y*points[j].y) 
                        + Math.sqrt((points[i].x-points[j].x)*(points[i].x-points[j].x) + (points[i].y-points[j].y)*(points[i].y-points[j].y));
                min = Math.min(min, temp);
            }
        }
        System.out.println(String.format("%.6f", min));
    }
}

Purpose:

Understand what an enumeration is, Although it is listed one by one, there are still ways to optimize it based on reality.

For example, the two-layer loop in this question only enumerates half of the situation: because what is sought is the distance, which has nothing to do with the two endpoints.

Thinking:

What should we do if there are more than two treasure chests that need to be obtained? ? ? You can refer to the next question.

Algorithm question 3:

Digital coloring

Difficulty ⭐⭐⭐

Xiaohong got a positive integer X. She could dye some of the digits red. Then she wanted the sum of all the digits colored red to be equal to the sum of the undyed digits.

She didn’t know if she could achieve her goal. Can you tell her?

Input description:

A positive integer X, 1Output description:

The output "Yes" is On the premise that Xiaohong can complete the dyeing as required. Otherwise, "No" is output.

Example 1

Input

1234567

Output

Yes

Instructions

Just dye 3, 4, and 7 red, so 3 4 7=1 2 5 6

Example 2

Input

23

Output

No

Description

显然无论如何都不能完成染色。

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Long x= Long.parseLong(br.readLine());
        //循环0到2^18来展现所有的可能性
        for(int i=0;i<1<<19;i++){
            long p=i,s1=0,s2=0,temp=x;
 
            //将p拟化为2进制，通过j来寻尾。寻一次p就对应的二进制数就少一位。
            for(int j=0;j<19;j++){
                if(p%2==1)s1+=temp%10;
                else s2+=temp%10;
                p/=2;
                temp/=10;
            }
            if(s1==s2){
                System.out.println("Yes");
                System.exit(0);
            }
        }
        System.out.println("No");
    }
}

这题使用的是状压枚举

只有两种状态就拟成2进制，假如有3种状态就拟成3进制（上面的代码会有些许改变，n种状态也一样）

 for(int i=0;i<1<<19;i++)  
//修改成
 for(int i=0;i<19;i++) p1[i]=p1[i-1]*3;
 for(int i=0;i<p1[i];i++){}

当然这题也可以使用背包或dfs来解答。

算法题4： 

ranko的手表  

难度 ⭐⭐⭐⭐

ranko 的手表坏了，正常应该显示 xx:xx 的形式（4 个数字），比如下午 1 点半应该显示 13:30 ，但现在经常会有一些数字有概率无法显示。

Ranko checked the time at t1 and then again at t2 after some time had passed.。她想弄清楚t1和t2两个时间点之间的最大和最小时间间隔是多少

保证t1在t2之前（且t1和t2不等）。 t1和t2在同一天的 00:00 到 23:59 之间。 

输入描述:

两行输入两个时间，为 xx:xx 的形式。x可以是数字或字符'?'，当为'?'时表示该数字未显示。保证输入是合法的。

输出描述:

一行输出两个整数，分别代表 t1 和 t2 相距时间的最小值和最大值（单位分钟）。

示例1

输入

18:0?

2?:1?

输出

121 319

说明

相距最小的时间为 18:09 到 20:10 ，相距121分钟。

相距最大的时间为 18:00 到 23:19 ，相距319分钟。

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();
        String s2 = br.readLine();
        ArrayList<Integer> a1 = new ArrayList<>();
        ArrayList<Integer> a2 = new ArrayList<>();
        for(int i = 0; i < 60*24; i++){
            int hour = i/60, minute = i%60;
            if((hour/10 == s1.charAt(0)-&#39;0&#39; || s1.charAt(0) == &#39;?&#39;) &&
               (hour%10 == s1.charAt(1)-&#39;0&#39; || s1.charAt(1) == &#39;?&#39;) &&
               (minute/10 == s1.charAt(3)-&#39;0&#39; || s1.charAt(3) == &#39;?&#39;) &&
               (minute%10 == s1.charAt(4)-&#39;0&#39; || s1.charAt(4) == &#39;?&#39;)) a1.add(i);
            if((hour/10 == s2.charAt(0)-&#39;0&#39; || s2.charAt(0) == &#39;?&#39;) &&
               (hour%10 == s2.charAt(1)-&#39;0&#39; || s2.charAt(1) == &#39;?&#39;) &&
               (minute/10 == s2.charAt(3)-&#39;0&#39; || s2.charAt(3) == &#39;?&#39;) &&
               (minute%10 == s2.charAt(4)-&#39;0&#39; || s2.charAt(4) == &#39;?&#39;))a2.add(i);
        }
        int min= Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for(int i = 0; i<a1.size();i++){
            for(int j = 0; j<a2.size();j++){
                if(a1.get(i)<a2.get(j)){
                    min = Math.min(min,a2.get(j)-a1.get(i));
                    max = Math.max(max,a2.get(j)-a1.get(i));
                }
            }
        }
        System.out.print(min + " " + max);
    }
}

The above is the detailed content of How to use greedy and enumeration in Java. For more information, please follow other related articles on the PHP Chinese website!

Statement：
This article is reproduced at:yisu.com. If there is any infringement, please contact admin@php.cn delete
Previous article：How to improve Java string encoding and decoding performanceNext article：How to improve Java string encoding and decoding performance

Related articles

See more