(Javaベース)アルゴリズムの貪欲アルゴリズム——活動手配問題

欲張りアルゴリズム(Greedy Algorithm):欲張りアルゴリズムとも呼ばれます.欲張りアルゴリズムとは、問題を解くときに、いつも当期的に見て最良の選択をすることです.つまり、欲張りアルゴリズムは最良の次のステップを決定することができ、全体的な最適性から考えるのではなく、ある意味での局所的な最適解だけです.
いくつかの問題において,貪欲なアルゴリズムでも原問題の最適解が得られることに注目すべきである.
アクティビティスケジュールの問題の説明:
n個のアクティビティの集合E={1,2,......,n}が設けられており,各アクティビティが同じリソースを使用する場合,同じ時間に1つのアクティビティしか使用できない.各アクティビティiには、対応する開始時間siと終了時間fiがあり、si
欲張り戦略:一番早い終了時間優先(一番遅い開始時間優先でもいいですが、原理的には同じです)
定義:s[]は開始時間、f[]は終了時間、nはアクティビティ数
準備作業:まずf[]をソートし、s[]とf[]を一致させる
以下にコードを貼ります.ソートはこのブログの以前のブログを調べることができるので、提供しません.そのため、わずか数行しかありません.

public static int[] GreedyAc(int s[], int f[], int n){
	int x[] = new int[n];
	x[0] = 1;
	int j = 0; //j    f      
	for(int i = 1; i < n; i++){
		//                         
		if(s[i] >= f[j]){
			x[i] = 1;
			j = i;
		}
	}
	return x;
}

また、欲張りアルゴリズムにも0-1リュックサック問題に似たリュックサック問題がありますが、リュックサック問題の要求は0-1リュックサック問題の要求とは異なり、リュックサック問題は必ずしも荷物全体をリュックサックに入れる必要はなく、荷物を一部に分けてリュックサックに入れることができます.欲張り戦略はViとWiの比を優先するように設計すればよい.
何か悪いところがあったり、もっと良いアドバイスがあったりしたら、コメントを歓迎します.