C++贪心算法实现活动安排问题

yuanran0 2019-11-04

_(:з」∠)_

#include <cstdio>
#include <iostream>
#include <ctime>
#include <windows.h>
#include <algorithm>
#include <fstream>
using namespace std;
struct activity
{
    int no;
    int start;
    int finish;
};
bool cmp(const activity &x, const activity &y)
{
    return x.finish<y.finish;//从小到大排<,若要从大到小排则>
}
int greedySelector(int m,int solution[],struct activity activity[]){
    int number = 1;
    solution[0] = 1;
    int i,j = 0,counter = 1;
    for(i = 1;i < m ;i++)
    {
        if(activity[i].start >=activity[j].finish)
        {
            solution[i] = 1;
            j = i;
            counter++;
        }
        else
            solution[i] = 0;
    }
    cout << "The amount of activities is:"<<counter<<endl;
    cout << "The solution is:";
    for(i = 0 ;i < m ;i++)
    {
       if (solution[i] == 1)
       {
            cout << activity[i].no <<" ";
       }
    }
    return counter;
}
int main(void)
{
    LARGE_INTEGER nFreq;
    LARGE_INTEGER nBeginTime;
    LARGE_INTEGER nEndTime;
    ofstream fout;
    srand((unsigned int)time(NULL));
    int m,i,j,t;
    double cost;
    cout << "Please enter the number of times you want to run the program:";
    cin >> t;
    fout.open("activity.txt",ios::app);
    if(!fout){
        cerr<<"Can not open file ‘activity.txt‘ "<<endl;
        return -1;
    }
    fout.setf(ios_base::fixed,ios_base::floatfield);       //防止输出的数字使用科学计数法
    for (j = 0;j < t;j++)
    {
        cout << "——————————————————The "<< j + 1 << "th test —————————————————"<<endl;
        m = 1 + rand()%100000;
        fout<<m<<",";
        int solution[m];
        activity activity[m];
        for( i = 0;i < m;i++)
        {
            activity[i].no = i+1;
            activity[i].start = 1 + rand()%1000;
            while(1)
            {
                activity[i].finish = 1 + rand()%10000;
                if(activity[i].finish > activity[i].start) break;
            }
        }
        QueryPerformanceFrequency(&nFreq);
        QueryPerformanceCounter(&nBeginTime);
        sort(activity,activity+m,cmp);
        greedySelector(m,solution,activity);
        QueryPerformanceCounter(&nEndTime);
        cost=(double)(nEndTime.QuadPart - nBeginTime.QuadPart) / (double)nFreq.QuadPart;
        fout << cost << endl;
        cout << "\nThe running time is:" << cost << " s" << endl;
    }
    fout.close();
    cout << endl << endl;
    cout << "Success!" << endl;
    return 0;
}

相关推荐