← back to writing

问题描述：#

某学科老师布置了n个题目，每个题目都有相应的分数及截止日期。各个题目的分数及截止日期可能并不相同。对某题目而言，如果在该题目的截止日期前完成则可获得对应的分数，否则无法得分。假设每个题目均需要花费一天的时间来完成，这期间无法完成其他题目。请你设计算法指定题目的完成计划，从而使总的得分最大。 下面给出一个包含了7个题目及相应的分数、截止日期的实例：

对该实例而言，得分最大的作业完成方案为花费4天时间依次完成题目2,6,3,7。得分为15。

【输入形式】

输入数据第一行为一个整数n (0 <= n <= 10000), 表示题目数目 之后n行各有两个整数, 第i行为 pi, di (1 <= pi, di <= 10000)，分别表示第i个题目的分数和截止时间

【输出形式】

一个整数, 为当前条件下的最大得分

【样例输入】

4 50 2 10 1 20 2 30 1

【样例输出】

80

分析#

本题适合用贪心算法来求解，先按照任务价值从大到小排序，然后依次取出后对任务进行判断。如果取出任务截至当天未被占用，则将该任务价值加入总价值后将当天标记为占用。如果之前判断的时间被占用，则往前推算一天后再进行判断。

伪代码#

对于i = 0 ~ n{
如果任务i截止日期当天没有被占用{
    结果加上第i个任务的分数
    任务i截止日期当天标记为已被占用;
}
如果任务截止日期当天被占用{
    对于j = 任务i截止日期-1 ~ 0){
        如果第j天被占用{
            结果加上第i个任务的分数
            第j天标记为已被占用
            跳出循环
        }
    }
}

代码（JAVA1）#

deadline类：#

test类：#

代码（JAVA2）#

代码（C++1）#

代码（C++2）#

算法正确性分析#

本算法对规定范围下不同的输入数据能够得出满足要求的结构，对于精心选择的典型、苛刻而带有刁难性的输入数据能够得出满足要求的结果，对于一切合法的输入数据都产生满足要求的结果。
对于核心算法，先按照任务价值从大到小排序，然后依次取出后对任务进行判断。如果取出任务截至当天未被占用，则将该任务价值加入总价值后将当天标记为占用。如果取出任务截止当天被占用，则往前推算一天进行判断。

总结#

本题采用贪心算法，通过这次学习，我了解到贪心算法需要建立数学模型来描述问题；把求解的问题分成若干个子问题；对每一子问题求解，得到子问题的局部最优解；把子问题的解局部最优解合成原来解问题的一个解。解决问题需要从问题的某个初始解出发，采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模，最后将所有部分解综合起来，得到问题的最终解。