编程介的小学生 2017-03-31 10:48 采纳率: 20.5%
浏览 769
已采纳

Loan Scheduling

The North Pole Beach Bank has to decide upon a set App of mortgage applications. Each application a∈App has an acceptance deadline da, ie. the required loan must be paid at a time ta, 0 <= ta <= da. If the application is accepted the Bank gets a profit pa. Time is measured in integral units starting from the conventional time origin 0, when the Bank decides upon all the App applications. Moreover, the Bank can pay a maximum number of L loans at any given time. The Bank policy if focussed solely on profit: it accepts a subset S⊆App of applications that maximizes the profit . The problem is to compute the maximum profit the Bank can get from the given set App of mortgage applications.

For example, consider that L = 1, App = {a,b,c,d}, (pa,da) = (4,2), (pb,db) = (1,0), (pc,dc) = (2,0), and (pd,dd) = (3,1). The table below shows all possible sets of accepted mortgage applications and the scheduling of the loan payments. The highest profit is 9 and corresponds to the set {c,d,a}. The loan requested by the application c is paid at time 0, the loan corresponding to d is paid at time 1, and, finally, the loan of a is paid at time 2.

Time Sets of accepted applications and loan scheduling
0 a b c d b c b b c c d d a b c
1 a d d d a a a d d d d
2 a a a a a a a
Profit 4 4 4 1 2 3 3 4 5 5 5 6 6 7 7 7 7 8 9

Input

Write a program that reads sets of data from an input text file. Each data set corresponds to a set of mortgage applications and starts with two integers: 0 <= N <= 10000 that shows the number of applications in the set, and 0 <= L <= 100 which shows the maximum number of loans the Bank can pay at any given time. Follow N pairs of integers pi di, i = 1..N, that specify the profit 0 <= pi <= 10000 and the deadline 0 <= di <= 10000 of the application i. Input data are separated by white spaces, are correct, and terminate with an end of file.

Output

For each data set the program computes the maximum profit the Bank can get from the accepted mortgage applications corresponding to that data set. The result is printed on standard output from the beginning of a line. There must be no empty lines on output. An example of input/output is shown below.

Sample Input

4 1 4 2 1 0 2 0 3 1

7 2
200 1 200 1 100 0 1000 2 80 1
50 20 500 1

0 100

1 0 4 1000
Sample Output

9
2050
0
0

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-04-09 15:34
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥50 汇编语言除法溢出问题
  • ¥65 C++实现删除N个数据列表共有的元素
  • ¥15 Visual Studio问题
  • ¥15 state显示变量是字符串形式,但是仍然红色,无法引用,并显示类型不匹配
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗