算法导论16.1 活动选择问题

系统管理员 2022-04-05 14:29 159阅读 0赞

这篇文章主要讲述一个经典问题：活动选择问题。并给出该问题的贪心算法实现和动态规划实现。

对于该问题的描述，在算法导论第16章给出了详细的讲解，这里就不做解释说明了，下面给出贪心算法的Java语言实现：

package chapter1.homework1;
    import java.util.*;
    
    public class ActivitySelector {
    
    	private int activitiesNum=0;//活动总数
    	private Activity[] activities=null;//记录所有活动，包括虚拟活动
    	
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		ActivitySelector sample=new ActivitySelector();
    		sample.getInputInfo();
    		System.out.println("活动选择结果：");
    		sample.greedyActivitySelector();
    	}
    	
    	public void greedyActivitySelector(){
    		int i=0;
    		for(int m=1;m<=this.activitiesNum;m++){
    			if(this.activities[m].start>=this.activities[i].end){
    				System.out.println("id="+this.activities[m].id+" start="+this.activities[m].start+" end="+this.activities[m].end);
    				i=m;
    			}
    		}
    	}
    	
    	public void getInputInfo(){
    		System.out.println("请输入活动的总数");
    		Scanner in=new Scanner(System.in);
    		this.activitiesNum=in.nextInt();
    		System.out.println("请依次输入活动的序号，活动的起始时间和活动的截止时间");
    		activities=new Activity[this.activitiesNum+1];
    		int id,start,end;
    		activities[0]=new Activity(0,0,0);
    		for(int i=1;i<this.activitiesNum+1;i++){
    			id=in.nextInt();
    			start=in.nextInt();
    			end=in.nextInt();
    			activities[i]=new Activity(id,start,end);
    		}
    	}
    	
    	public class Activity{
    		private int id;
    		private int start;
    		private int end;
    		
    		public int getId() {
    			return id;
    		}
    		public int getStart() {
    			return start;
    		}
    		public int getEnd() {
    			return end;
    		}
    		
    		public Activity(int id,int start,int end){
    			this.id=id;
    			this.start=start;
    			this.end=end;
    		}
    	}
    }

上述代码是按照算法导论书中GREEDY-ACTIVITY-SELECTOR(s,f)伪代码实现的，大家可以参考下，运行结果如下所示：

请输入活动的总数
    11
    请依次输入活动的序号，活动的起始时间和活动的截止时间
    1 1 4
    2 3 5
    3 0 6
    4 5 7
    5 3 8
    6 5 9
    7 6 10
    8 8 11
    9 8 12
    10 2 13
    11 12 14
    活动选择情况如下：
    id=1 start=1 end=4
    id=4 start=5 end=7
    id=8 start=8 end=11
    id=11 start=12 end=14

在课后练习题16.1-1中，要求给出活动选择问题的动态规划算法，下面就给出动态规划的算法。

在动态规划算法中，我们要利用到书中公式16.3，并且要定义数组c\[i\]\[j\]来保存在活动ai之后，活动aj之前的最大活动子集的数目。

算法实现如下所示：

package chapter1.homework1;
    
    import java.util.Scanner;
    
    public class ActivitySelectorDP {
    
    	private int activitiesNum=0;//活动总数
    	private Activity[] activities=null;//记录所有活动，包括虚拟活动
    	private int c[][]=null;//定义数组存储
    	
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		ActivitySelectorDP sample=new ActivitySelectorDP();
    		sample.getInputInfo();
    		sample.dynamicProgramming();
    		System.out.println("活动选择情况如下：");
    		sample.printSelectedActivity(0, sample.activitiesNum+1);
    	}
    	
    	public void getInputInfo(){
    		System.out.println("请输入活动的总数");
    		Scanner in=new Scanner(System.in);
    		this.activitiesNum=in.nextInt();
    		System.out.println("请依次输入活动的序号，活动的起始时间和活动的截止时间");
    		activities=new Activity[this.activitiesNum+2];
    		int id,start,end;
    		activities[0]=new Activity(0,0,0);
    		for(int i=1;i<this.activitiesNum+1;i++){
    			id=in.nextInt();
    			start=in.nextInt();
    			end=in.nextInt();
    			activities[i]=new Activity(id,start,end);
    		}
    		activities[this.activitiesNum+1]=new Activity(this.activitiesNum+1,Integer.MAX_VALUE,Integer.MAX_VALUE);
    	}
    	
    	public void dynamicProgramming(){
    		this.c=new int[this.activitiesNum+2][this.activitiesNum+2];
    		for(int i=0;i<=this.activitiesNum;i++){
    			c[i][i+1]=0;
    		}
    		for(int step=2;step<=this.activitiesNum+1;step++){
    			for(int i=0;i<=this.activitiesNum;i++){
    				int j=i+step;
    				if(j<this.activitiesNum+2){
    					if(this.activities[i].end<=this.activities[j].start){
    						int max=0;
    						for(int k=i+1;k<j;k++){
    							if(this.activities[k].start>=this.activities[i].end
    									&&this.activities[k].end<=this.activities[j].start){
    								int temp=c[i][k]+c[k][j]+1;
    								if(temp>max)
    									max=temp;
    							}
    						}
    						if(max>c[i][j]){
    							c[i][j]=max;
    						}
    					}
    				}
    			}
    		}
    	}
    	
    	public void printSelectedActivity(int start,int end){
    		if(end-start==1){
    			return;
    		}
    		for(int k=start+1;k<end;k++){
    			if(this.activities[k].start>=this.activities[start].end
    					&&this.activities[k].end<=this.activities[end].start){
    				if(c[start][k]+c[k][end]+1==c[start][end]){
    					printSelectedActivity(start,k);
    					System.out.println("id="+k+" start="+this.activities[k].start+" end="+this.activities[k].end);
    					printSelectedActivity(k,end);
    					break;
    				}
    			}
    			
    		}
    	}
    	
    	public class Activity{
    		private int id;
    		private int start;
    		private int end;
    		
    		public int getId() {
    			return id;
    		}
    		public int getStart() {
    			return start;
    		}
    		public int getEnd() {
    			return end;
    		}
    		
    		public Activity(int id,int start,int end){
    			this.id=id;
    			this.start=start;
    			this.end=end;
    		}
    	}
    }

程序运行结果如下所示：