一、实验内容及要求
1.要求按贪心算法原理求解问题;
2.要求手工输入s[10]及f[10],其中注意自己判断s[i]<f[i];
3.要求显示所有活动及最优活动安排的i事件列表。
二、实验步骤
1、手工输入活动事件;
2、输出活动s数组及f数组;
2、计算最优活动安排后,输出最优i事件列表。
输入:
请输入s数组:
请输入f数组:
输出
s=15,3,2,8.....
f=18,5,4,10.....
i=1,5,8
Java源代码:
package shiyan;
import java.util.Scanner;
public class shiyan3 {
public static void main(String[] args) {
int number=10; //活动数量10个
int[] s = new int[number]; //开始时间数组
int[] f = new int[number]; //结束时间数组
System.out.println("请分别输入"+number+"个活动的开始时间:");
Scanner in_s = new Scanner(System.in);//循环输入开始时间数组
for(int i=0;i<number;i++){
s[i]=in_s.nextInt();}
System.out.println("请分别输入"+number+"个活动的结束时间:");
Scanner in_f = new Scanner(System.in);//循环输入结束时间数组
for(int i=0;i<number;i++){
f[i]=in_f.nextInt();}
System.out.println("开始时间数组s[10]:");
for(int i=0;i<number;i++){ //输出两个数组
System.out.print("["+s[i]+"]"); }
System.out.println("\n结束时间数组f[10]:");
for(int i=0;i<number;i++){
System.out.print("["+f[i]+"]"); }
boolean[] a=new boolean[s.length]; //一个与活动数目等长的 boolean型数组记录每个活动的状态
shiyan3 ac = new shiyan3();
int counts=ac.Activity_arrangement(s, f, a);
System.out.println("\n活动集合中最大相容活动数量为:"+counts);
for(int i=1;i<=s.length-1;i++){
if(a[i]){
System.out.println("第"+i+"活动被选中,其开始时间为:"+s[i-1]+",结束时间为:"+f[i-1]); } } }
public int Activity_arrangement(int[] s,int[] f,boolean[] a){
int n=s.length-1;
a[1]=true; //第一个活动被选中
int j=1;
int count=1; //被选中活动的数量,默认第一个活动被选中
for(int i=2;i<=n;i++){
if(s[i]>=f[j]){ //下一个活动开始时间大于大于等于上一个活动结束时间
a[i]=true;
j=i;
count++; }
else{
a[i]=false;
}
}
return count;
运行结果如下: