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

Bertha 。 2022-02-20 00:07 368阅读 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 */