算法概论实验九 贪心法

算法概论实验

实验九
实验目的与要求：
（1） 掌握贪心法的基本思想和设计方法。
1．区间划分问题
【问题描述】
给定一组报告，其中的每个报告设置了一个开始时间si和结束时间fi。设计与实现一个算法，对这组报告分配最少数量的教室，使得这些报告能无冲突的举行。
2．最小延迟调度问题
【问题描述】
    假定有一单个的资源在一个时刻只能处理一个任务。现给定一组任务，其中的每个任务i包含一个持续时间ti和截止时间di。设计与实现一个算法，对这组任务给出一个最优调度方案，使其对所有任务的最大延迟最小化。

1．区间划分问题

#include<iostream>
using namespace std;
#define N 100
struct Report
{
    int num;//报告编号
    int begin;//开始时间
    int end;//结束时间
    bool flag;//是否已分配教室
    int classroom;//教室号
};
void QuickSort(Report* rep,int f,int t)//一开始将所有报告按结束时间排序
{
    if(f<t)
    {
        int i=f-1,j=f;
        Report r=rep[t];
        while(j<t)
        {
            if(rep[j].end<=r.end)
            {
                i++;
                Report tmp=rep[i];
                rep[i]=rep[j];
                rep[j]=tmp;
            }
            j++;
        }
        Report tmp1=rep[t];
        rep[t]=rep[i+1];
        rep[i+1]=tmp1;
        QuickSort(rep,f,i);
        QuickSort(rep,i+2,t);
    }
}
int select_room(Report *rep,int *time,int n)
{
    //第一个报告分给第一个教室
    int i=1,j=1;//i报告，j教室
    int sumRoom=1;
    int sumRep=1;//教室已分配的报告数
    time[1]=rep[0].end;
    rep[0].classroom=1;
    for(i=1;i<n;i++)
    {
        for(j=1;j<=sumRoom;j++)
        {
            if((rep[i].begin>=time[j])&&(!rep[i].flag))
            {
                rep[i].classroom=j;
                rep[i].flag=true;
                time[j]=rep[i].end;
                sumRep++;
            }
        }
        if(sumRep<n&&i==n-1)//报告没有分配完
        {
            i=0;
            sumRoom++;
        }
    }
    return sumRoom;
}
int main()
{
    int n;
    Report rep[N];
    int time[N];//每个教室最后一个报告的结束时间
    cout<<"请输入报告数量:"<<endl;
    cin>>n;
    int i;
    for(i=0;i<n;i++)
    {
        //初始化
        time[i+1]=0;//time[1]~time[10]
        rep[i].num=i+1;//编号1~10
        rep[i].flag=false;
        rep[i].classroom=0;
        cout<<"报告"<<i+1<<"开始时间:";
        cin>>rep[i].begin;
        cout<<"报告"<<i+1<<"结束时间:";
        cin>>rep[i].end;
    }
    QuickSort(rep,0,n-1);
    int roomNum=select_room(rep,time,n);
    cout<<"所用教室总数为:"<<roomNum<<endl;
    for(i=0;i<n;i++)
    {
        cout<<"活动"<<rep[i].num<<"在教室"<<rep[i].classroom<<"中"<<endl;
    }
    system("pause");
    return 0;
}

2．最小延迟调度问题

#include<iostream>
using namespace std;
#define N 100
struct Mission
{
    int num;
    int last;
    int end;
};
void QuickSort(Mission *mi,int f,int t)
{
    if(f<t)
    {
        int i=f-1,j=f;
        Mission m=mi[t];
        while(j<t)
        {
            if(mi[j].end<=m.end)
            {
                i++;
                Mission tmp=mi[i];
                mi[i]=mi[j];
                mi[j]=tmp;
            }
            j++;
        }
        Mission tmp1=mi[t];
        mi[t]=mi[i+1];
        mi[i+1]=tmp1;
        QuickSort(mi,f,i);
        QuickSort(mi,i+2,t);
    }
}
int main()
{
    int n;
    cout<<"请输入任务总数:"<<endl;
    cin>>n;
    Mission mi[N];//Mission[0]~Mission[n-1]
    int start[N+1];//排好序的任务的开始时间，start[1]~start[n]
    int i;
    for(i=0;i<n;i++)
    {
        mi[i].num=i+1;
        cout<<"任务"<<i+1<<"的持续时间为:";
        cin>>mi[i].last;
        cout<<"任务"<<i+1<<"的截止时间为:";
        cin>>mi[i].end;
    }
    QuickSort(mi,0,n-1);
    int delay=0;
    start[1]=0;
    if(start[1]+mi[0].last>mi[0].end)
    {
        delay+=start[1]+mi[0].last-mi[0].end;//如果开始时间+持续时间>截止时间，累计延迟
    }
    for(i=1;i<n;i++)
    {
        start[i+1]=start[i]+mi[i-1].last;
        if(start[i+1]+mi[i].last>mi[i].end)
        {
            delay+=start[i+1]+mi[i].last-mi[i].end;
        }
    }
    cout<<"延迟最小为:"<<delay<<endl;
    for(i=0;i<n;i++)
    {
        cout<<"任务"<<mi[i].num<<"的执行时间:["<<start[i+1]<<","<<mi[i].last+start[i+1]<<"]"<<endl;
    }
    system("pause");
}