10346 带价值的作业安排问题

时间限制:1000MS 代码长度限制:10KB
提交次数:25 通过次数:9

题型: 编程题 语言: G++;GCC;VC;JAVA

Description

已知n项作业E={1, 2, … ,n} 需要完成，只有一台机器，同一时刻至多完成一个作业，
而且每项作业需要的时间都是单位时间1。第k项作业要求在时间fk时刻执行并完成，而且
完成这项作业将获得效益pk，（k=1, 2, … , n）。

E的子集称为相容的，如果它们可以被安排由一台机器完成。

带限期和价值的作业安排问题就是：要在所给的作业集合中选出总效益值最大的相容子集，
请输出最大的总效益值。

输入格式

输入3行：
第一行，一个数n，表示n个作业（n<10000）。
第二行，n个正数，表示这n个作业的应执行的时间点。
第三行，n个正数，表示这n个作业的效益值。

输出格式

输出：相容作业子集所获得的最大总效益。

例如：7个作业
时间点和效益值分别是：
1 8 8 5 9 3 5
20 25 30 7 18 10 18
则：可以获得的最大总效益为：20 + 30 + 18 + 10 + 18 = 96

输入样例

7
1 8 8 5 9 3 5
20 25 30 7 18 10 18

输出样例

96

解题思路

贪心算法

这题较简单，求总效益值最大的相容子集，即把重复的元素集合中效应较小的给去除即可。

算法思路

1. 初始化三个数组，time 一个记录各时间节点，val 记录各节点效应，all 用于打表，记录相应时间节点（下标）是否有效应
2. 如果 all 数组该时间节点值为0，说明该时间节点第一次记录效应，直接加入即可
3. 如果 all 数组该时间节点值不为0，说明该时间节点不是第一次记录效应，即需要去重，条件是如果新来的效应如果较大，就代替原本的，否则保持原来的效应不变
4. 在进行上面循环遍历的同时记录总效应 sum 即可

更多注释可查看下方的完整代码中，有助于理解。

代码如下

#include 
#include using namespace std;int main()
{int time[10001]; // 记录各时间节点int val[10001]; // 记录各节点效应int all[10001]; // 打表，记录相应下标是否有效应memset(all, 0,sizeof(all));int i, n, nowTime, res = 0;cin >> n;for(i = 1; i <= n; i++) {cin >> time[i];}for(i = 1; i <= n; i++) {cin >> val[i];}for(i = 1; i <= n; i++) {nowTime = time[i]; // 当前时间节点// 首次记录该时间的效应，直接加入即可if(all[nowTime] == 0) {all[nowTime] = val[i];res += all[nowTime];} else {// 再次记录该时间的效应，应判断是否比原本的大，大才加入if(val[i] > all[nowTime]) {res -= all[nowTime]; // 把原来的减掉后，后面再加上即更新成最新的效应all[nowTime] = val[i];res += all[nowTime];}}}cout << res << endl;return 0;
}

最后

对我感兴趣的小伙伴可查看以下链接

• 我的掘金主页：https://juejin.cn/user/1302297507801358
• 博客主页：http://blog.zhangjiancong.top/
• 公众号：Smooth前端成长记录