検索

ホームページ >Java >＆＃＆チュートリアル >Javaで貪欲と列挙を使用する方法

Javaで貪欲と列挙を使用する方法

王林
王林転載
2023-05-20 11:46:461096ブラウズ

筆記試験のスキル: データ範囲に基づいて知識ポイントを推測する方法を学ぶ# ペンでの質問）。

##n 20 以内の範囲: ##3 次元 dpO(n^2)二次元 dp バックパック列挙二次元プレフィックスなどO(n√n)#n 範囲 1e6 以内: O(nlogn)#約数と約数の数を求める

#O(n*2^n)

 #圧力探索 /dfs 爆発探索

n 範囲 200 以下:
O(n ^ 3)

n 範囲 3000 以内:

# #n 範囲 1e5 以下:

##因子などの暴力的な検索

バイナリの答えはさまざまな stl を使用しますオイラーふるいなどを見つけます

##n 範囲 1e7 以内:

O(n)
デュアルポイントニードル線形 DP 差動/プレフィックスおよび 1e14 内の

# N 範囲:

((√N )

貪欲:

貪欲とは、あらゆる段階で最善の選択をすることを意味します。一般に解決される問題には、次のような特徴があります。局所的な最適性が全体的な最適性につながる可能性があります。

貪欲は万能薬ではないことに注意してください。

アイテムは n 個あります。各項目には値 v[i] と重み w[i] があります。

次に、総重量が m を超えないアイテムを取り出します。取り出したアイテムの最大値はいくらですか? (ナップザック問題)

  • 戦略 1: 値の降順に並べ、毎回最大の値を取得します。

  • 戦略 2: 重量の昇順に並べ、毎回最も軽い重量を選択します。

  • 戦略 3: 価値/重量 (つまり、単位値) に従って降順に並べ、毎回最も単位値が高いものを選択します。

列挙:

1. 単純な列挙

名前が示すように、for ループを使用してすべての状況を列挙します。

2. ステータスの列挙

n 進法のプロパティを使用して列挙します。

適切なシナリオ: 合計 n 個のアイテムがあり、各アイテムには m 個の状態があり、すべてのアイテムのすべての状態を列挙し、複雑さは O(m^n) です。

バイナリ列挙の書き方:

古典的な問題: n 個の数値 a1、a2...an が与えられた場合、各数値はオプションであり、考えられるすべての解決策をリストします。 

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;            //求下一个二进制位
     	}
     //这里可以添加想要的操作。
   }

アルゴリズムの質問 1:

チカとサツマ (PriorityQueue Comparator の使用)

難易度 ⭐⭐

チカはサツマを食べるのがとても好きです。みかんにはそれぞれある程度の酸味と甘みがあり、千歌は甘いものは好んで食べますが、酸っぱいものは苦手です。

千花は k 個のみかんを食べました。合計 n 個のみかんがあります。彼女は食べたみかんの甘みと酸味の合計を計算します。チカは可能な限り最大の甘さの合計を取得したいと考えています。複数の選択肢がある場合、彼女は総酸性度をできるだけ小さくしたいと考えています。

彼女が知りたいのは、最終的な総酸味と総甘味は何でしょうか?

質問情報: 最初に甘味の降順、次に酸味の昇順で並べ替えます (前回の甘味の降順を維持し、次に酸味の昇順)

説明を入力してください:

最初の行には 2 つの正の整数 n と k があり、それぞれみかんの総数とチカが食べたみかんの数を表します。 (1≤k≤n≤200000)

2行目は、各みかんの酸味を表すn個の正の整数aiが入っています。 (1≤ai≤1e9)

2行目はn個の正の整数biで、みかんの甘さを表しています。 (1≤bi≤1e9)

出力の説明:

スペースで区切られた 2 つの正の整数。それぞれ総酸味と総甘味を表します。

例

入力

3 2

1 3 4

2 2 5

出力

5 7

説明

1番と3番のみかんを選択し、酸度の合計は5、合計は5です。甘さは 7 で、これが最適解です。 

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);
    }
}

目的:

貪欲とは何かを理解すると、優先順位を付けるように設計するときに、PriorityQueue Comparator の使用を検討できます。

アルゴリズムの質問 2:

あなたとヨット

難易度 ⭐⭐

あなたのお父さんは船長です。小さい頃から海が大好きだったんですね。その日、彼女は帆船に乗って出発した。

海にはたくさんの宝物があり、それぞれの宝物の座標はわかっています。初期座標は (0,0) です。彼女は 2 つの宝物を探索してから、原点に戻りたいと考えています。

ルートをできるだけ短くしたいと考えています。彼女が知りたかったのは、最短ルートの長さはどれくらいかということです。

質問情報: 2 つの for ループで列挙し、最短パスを保存します。

入力説明:

最初の行は、宝の数を表す正の整数 n です。 (2≤n≤2000)

次の n 行には、各行に 2 つの正の整数 xi と yi が含まれており、i 番目の宝物の座標を表します (-3000≤xi,yi≤3000)

同じ場所に 2 つの宝物が存在しないという保証はありません。つまり、同じ場所で両方の宝物を探索できるということです。

出力の説明:

最短パスの長さ。小数点以下は 6 桁にしてください。

例

入力

2

1 0

0 1

出力

3.414214

説明

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));
    }
}

目的:

列挙とは何かを理解します。 1 つずつリストされていますが、現実に基づいて最適化する方法はまだあります。

たとえば、この質問の 2 層ループは状況の半分だけを列挙しています。これは、求められるのは距離であり、2 つのエンドポイントとは何の関係もないためです。

思考:

取得する必要のある宝箱が 2 つ以上ある場合はどうすればよいでしょうか。 ? ?次の質問を参照してください。

アルゴリズムの問​​題 3:

デジタルぬりえ

難易度 ⭐⭐⭐

Xiaohong は正の整数 X を取得しました。彼女は数字のいくつかを赤く染めることができました。次に、赤く塗られたすべての数字の合計が、染まっていない数字の合計と等しくなるようにしたいと考えました。

彼女は目標を達成できるかどうかわかりませんでした。彼女に言ってもらえますか？

入力の説明:

正の整数 X, 1出力の説明:

出力「Yes」 Xiaohongが必要に応じて染色を完了できることが前提です。それ以外の場合は「No」が出力されます。

#例 1

入力

1234567

出力

はい

##手順

3、4、7を赤に染めるだけなので、3 4 7=1 2 5 6

例2

入力

23

出力

No

説明

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

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);
    }
}

以上がJavaで貪欲と列挙を使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明：
この記事はyisu.comで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。
前の記事：Java 文字列のエンコードとデコードのパフォーマンスを向上させる方法次の記事：Java 文字列のエンコードとデコードのパフォーマンスを向上させる方法

関連記事

続きを見る