带权的活动安排问题-利益最大化-DP-蒲公英云

带权的活动安排问题-利益最大化-DP

Bertha 。 2022-02-20 00:07 404阅读 0赞

基础的贪心问题-活动安排问题是这种问题的特殊情况（权值为1）。但这个问题不能用贪心算法而是应该用动态规划算法来求解。这种问题下的另一种较特殊情况是每段任务的权值是它的时间长度，使活动安排时间最满，同样要用到动态规划算法。

思路是：先将活动按照结束时间排序（和贪心类似），然后从第一个活动开始遍历这些任务，同时维护一个全局最大值，到每个活动结束的最大值。排序时间复杂度为O(nlogn)，后面一段时间复杂度为O(n)。

状态转移方程为
Ans = max(Ans, last + edges[i].val);
其中，Ans为全局最大值，last为截止到上一个和本任务不产生冲突的任务所保存的最大值。有几个边界条件需要注意。

代码（没有测过大量数据，不知道有没有bug，不过大方向应该是对的）

#include <iostream>
#include <algorithm>
using namespace std;
struct Edge { 
    int x, y, val, ans;
};
bool cmp(Edge a, Edge b) { 
    return a.y < b.y;
}
int main()
{ 
    int n;
    cin >> n;
    Edge *edges = new Edge[n];
    for (int i = 0; i < n; ++i) { 
        cin >> edges[i].x >> edges[i].y >> edges[i].val;
    }
    sort(edges, edges + n, cmp);
    int Ans = 0;
    for (int i = 0; i < n; ++i) { 
// cout << "now : " << edges[i].x << ' ' << edges[i].y << ' ' << edges[i].val << endl;
        int last = 0;
        for (int j = i - 1; j >= 0; j--) { 
            if (edges[i].x >= edges[j].y) {  // 假定边界是可以重合的 
                last = edges[i].ans;
// cout << "last = " << last << endl;
// cout << edges[i].val << endl;
                Ans = max(Ans, last + edges[i].val);
                break;
            }
            if (j == 0) Ans = max(Ans, last + edges[i].val); // 作为它的边界 
        }
        if (i == 0) Ans = max(Ans, last + edges[i].val); // 第一个数据，直接设为边界 
        edges[i].ans = Ans;
        cout << "Now the ans = " << Ans << endl;
    }
    cout << "The end ans = " << Ans << endl;
}
/* 3 1 4 2 7 10 3 2 6 8 */