活动安排问题
一问题分析
二代码实现 java
package greedySelctor;import java.io.BufferedWriter;
import java.io.FileWriter; import java.io.IOException; import java.util.Arrays; import java.util.Comparator;public class bin
{public static void main(String[] args) throws IOException{ // int []s= {0,1,3,0,5,3,5,6,8,8,2,12};
// int []f= {0,4,5,6,7,8,9,10,11,12,13,14}; int []s= {0,1,2,3,4,5,6}; int []f= {0,10,9,8,7,11,20}; element []ele=new element[s.length-1] ; for(int i=1; i<s.length; i++) { ele[i-1] =new element(s[i], f[i], i); } greedySelctor myGreedySelctor=new greedySelctor(ele); }}
class greedySelctor { element []ele; int count=0; //被安排活动的个数 public greedySelctor(element []ele) throws IOException { this.ele=ele; GreedySelctor(); display(); } public void GreedySelctor() { Arrays.sort(ele, new Comparator(){ //传入的时候由用户自己选 @Override public int compare(element o1, element o2) { // TODO Auto-generated method stub int finsh1 = o1.f; int finsh2 = o2.f; if (finsh1>finsh2) { return 1; } else { if (finsh1<finsh2) { return -1; }else { return 0; }} } }); ele[0].x=1; //第一个活动一定会被选上 int f=ele[0].f; count++; for(int i=1; i
}
class element //活动类 { int s; //开始时间 int f; //结束 int x; //是否被选中 int i; //编号 public element(int s,int f,int i) { this.s=s; this.f=f; this.i=i; } }三 运行结果
ele[0]: i: 1 s: 1 f: 4 x: 1 +++++++++++++++++++ ele[1]: i: 2 s: 3 f: 5 x: 0 +++++++++++++++++++ ele[2]: i: 3 s: 0 f: 6 x: 0 +++++++++++++++++++ ele[3]: i: 4 s: 5 f: 7 x: 1 +++++++++++++++++++ ele[4]: i: 5 s: 3 f: 8 x: 0 +++++++++++++++++++ ele[5]: i: 6 s: 5 f: 9 x: 0 +++++++++++++++++++ ele[6]: i: 7 s: 6 f: 10 x: 0 +++++++++++++++++++ ele[7]: i: 8 s: 8 f: 11 x: 1 +++++++++++++++++++ ele[8]: i: 9 s: 8 f: 12 x: 0 +++++++++++++++++++ ele[9]: i: 10 s: 2 f: 13 x: 0 +++++++++++++++++++ ele[10]: i: 11 s: 12 f: 14 x: 1 +++++++++++++++++++四 总结收获
-
贪心算法的关键在于问题具有贪心性质
-
学习到了对象数组排序的方法
Arrays.sort(ele, new Comparator(){ //传入的时候由用户自己选 @Override public int compare(element o1, element o2) { // TODO Auto-generated method stub int finsh1 = o1.f; int finsh2 = o2.f; if (finsh1>finsh2) { return 1; } else { if (finsh1<finsh2) { return -1; }else { return 0; }} }});具体解释见链接(https://blog.csdn.net/qq_37937537/article/details/80445731)
五 不足
代码写的不够熟练