数据结构：活动选择问题

太过爱你忘了你带给我的痛 2022-05-31 12:56 195阅读 0赞

# 活动选择问题 #

问题是这样的，给定一系列的活动，给出可以完成的最多的活动的数量。做法直接贪心即可，按照结束时间排序，然后选择即可

# 代码如下 #

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    
    //下面是活动选择问题的DP方法和贪心算法
    
    //表示一个活动的开始结束时间
    const int SIZE = 100;
    struct Activity
    {
        int beginTime;
        int endTime;
        Activity(int x, int y)
        {
            beginTime = x;
            endTime = y;
        }
    };
    
    //按照结束事件递增排序
    bool cmp(Activity x, Activity y)
    {
        return x.endTime <= y.endTime;
    }
    
    void GreedByLoop(vector<Activity> All);
    void DP(vector<Activity> All);
    void printRes(int c[SIZE][SIZE], int x, int y, vector<int> &res);
    
    
    int main()
    {
        const int SIZE = 12;
        //一共11个活动,最大的活动兼容集合是{a1,a4,a8,a11}和{a2,a4,a9,a11}
        //第一个的开始时间和结束时间0 0 是为了便于计算,特意添加的一个虚拟事件
        int beg[SIZE] = { 0,1,3,0,5,3,5,6,8,8,2,12 };
        int end[SIZE] = { 0,4,5,6,7,8,9,10,11,12,13,14 };
    
        vector<Activity> AllActivity;
        for (int i = 0; i<SIZE; i++)
            AllActivity.push_back(Activity(beg[i], end[i]));
        sort(AllActivity.begin(), AllActivity.end(), cmp);
    
        GreedByLoop(AllActivity);
    
        Activity one = Activity(15, 15);
        AllActivity.push_back(one);
        DP(AllActivity);
        AllActivity.pop_back();
    
        system("pause");
    }
    
    //Greedy算法循环实现
    //主要思想是选择尽量早早介绍的活动,这样可以留
    //更多的剩余时间去安排其他更多的活动,所以活动都是按照结束时间递增排序的
    //所以第一个活动必然在活动列表之内,然后依次安排其余的活动
    void GreedByLoop(vector<Activity> All)
    {
        vector<int> res;
        int k = 1;
        res.push_back(k);
        for (int i = 2; i<All.size(); i++)
        {
            //寻找下一个最早结束的活动
            if (All[i].beginTime >= All[k].endTime)
            {
                res.push_back(i);
                k = i;
            }
        }
        cout << endl << "By Loop Final Res is Following: " << endl;
        for (int i = 0; i<res.size(); i++)
            cout << res[i] << "  ";
        cout << endl;
    }
    
    // c[i][j]表示活动i介绍之后到活动j开始之前的活动的数量,
    // c[i][j]=c[i][k]+c[k][j]+1; 表示存在活动k在i和j之间,加入k不影响活动i和j,
    //那么就可以分解为c[i][k],c[k][j]两个子问题,
    //需要向头部和尾部添加两个虚拟活动
    void DP(vector<Activity> All)
    {
        int c[SIZE][SIZE] = { 0 };
        int ret[SIZE][SIZE] = { 0 };
    
        //要考头部的虚拟活动,所以j从1开始,到All.size()结束
        //这个要求i<j,而且k是在i和j之间,所以这个直接三层循环即可,这个和folyed算法的最优子结构很像
        for (int j = 1; j<All.size(); j++)
        {
            for (int i = 0; i<j; i++)
            {
                for (int k = i + 1; k<j; k++)
                {
                    if (All[k].beginTime >= All[i].endTime && All[k].endTime <= All[j].beginTime)
                    {
                        if (c[i][k] + c[k][j] + 1 > c[i][j])
                        {
                            c[i][j] = c[i][k] + c[k][j] + 1;
    
                            //记录分叉位置,便于递归查找
                            ret[i][j] = k;
                        }
    
                    }
                }
            }
        }
        int FinalNum = c[0][All.size() - 1];
        cout << endl << "By DP Nums is : " << FinalNum << endl;
    
        vector<int> res;
        printRes(ret, 0, All.size() - 1, res);
        cout << "By DP Final Res is Following: " << endl;
        for (int i = 0; i<res.size(); i++)
            cout << res[i] << "  ";
        cout << endl;
    
    }
    
    //递归查询
    void printRes(int c[SIZE][SIZE], int x, int y, vector<int> &res)
    {
        if (c[x][y] != 0)
        {
            int k = c[x][y];
            res.push_back(k);
            printRes(c, x, k, res);
            printRes(c, k, y, res);
        }
    }