时间与收益

Description

Given a set of n jobs where each job i has a deadline and profit associated to it. Each job takes 1 unit of time to complete and only one job can be scheduled at a time. We earn the profit if and only if the job is completed by its deadline. The task is to find the maximum profit and the number of jobs done.

Input

The first line of input contains an integer T denoting the number of test cases.Each test case consist of an integer N denoting the number of jobs and the next line consist of Job id, Deadline and the Profit associated to that Job.

Constraints:1<=T<=100，1<=N<=100，1<=Deadline<=100，1<=Profit<=500

Output

Output the number of jobs done and the maximum profit.

Sample Input 1

2
4
1 4 20 2 1 10 3 1 40 4 1 30
5
1 2 100 2 1 19 3 2 27 4 1 25 5 1 15

Sample Output 1

2 60
2 127

分析

题目解析：

• 给定N个工作，每个工作给出ID、截止日期和收益
• 每个单位时间只能完成一个任务，任务只有在截止日期前完成才有收益
• 问怎样安排任务能获得最大利润

错误思路：

• 如果每次都选择最大价值的任务话,那么就会有一些任务选不到,比如说第一次选择了截至时间为2的任务,那么第二次 就无法选择截至时间为1的任务(已经结束了)
  eg 2 100 1 90 如果选择100,第二次就无法选择90

• 如果每次都选择该时间内最大价值的任务,这样结果一定是每个时间由一个任务组成,那么就会漏解
  eg: 2 20 , 2 21, 1 10 ,1 11 如果选择11 21 就会漏掉20 21
  由题意可知,对于每个截至时间为N的工作我们最多选N次,

所以我们可以想到如下办法,

1. 第一次选择截至时间为1中最大的1个数

2. 第二次选择截至时间为2中最大的两个数,把第一次的最大值也算上,更新比较留下2个最大的

3. 第三次选择截至时间为3中最大的三个数,把第二次的最大值也算上,更新比较留下3个最大的

4. 依次类推,这样就能获得最佳的答案

但这样未免太复杂,并且如果截至时间为x中没有x个数,就会漏解,但根据此思路,有如下办法

解题思路：

1. 创建二维数组，按收益从大到小存放[日期，收益]
2. 创建一维标记数组，长度为最大截止日期
3. 遍历二维数组，每次取出最大收益，判断是否放入标记数组
   • 该截止日期位置值为0，即没有元素，则放入
   • 有元素则往前寻找空位置
   • 超出标记数组长度则舍弃
4. 遍历结束，标记数组的值就是要求的最大利润

参考

python

# 时间与收益
# 贪婪算法：每次得到最优解的一部分
# 需要一个一维标记数组，来标记各个时间点是否已有任务，存放收益
# 按收益排序，每次取出最大收益，判断把任务编号放入数组中


def timeAndProfit(arr):
    max_arr = []
    max_deadline = -1
    for i in range(0, len(arr), 3):
        if arr[i + 1] > max_deadline:
            max_deadline = arr[i + 1]   # 获取最大截至日期
        max_arr.append([arr[i + 1], arr[i + 2]])    # 构建[日期，收益]列表
    max_arr.sort(reverse=True, key = lambda x: x[1])    # 按收益排序
    dp = [0] * max_deadline # 标记数组，存放结果
    count = 0
    for tmp in max_arr:
        deadline = tmp[0] - 1   # 对应标记数组下标
        while deadline >= 0 and dp[deadline] != 0:
            deadline -= 1
        if deadline != -1:
            dp[deadline] = tmp[1]
            count += 1
    return count, sum(dp)
    


if __name__ == '__main__':
    for _ in range(int(input())):
        N = int(input())
        arr = list(map(int, input().split()))
        count, result = timeAndProfit(arr)
        print(count, result)
        

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