算法设计与分析 SCAU10346 带价值的作业安排问题

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

最后

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

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