超市

Grade 100 Open Time Thursday, 18 June 2020, 5:20 PM
Discount 0.8 Time Discount Thursday, 18 June 2020, 5:20 PM
Allow late Yes Close Time Thursday, 18 June 2020, 5:20 PM
Input file supermarket.in Output file supermarket.out

【题目描述】超市(supermarket)POJ 1456

一个超市有一个待售商品集合Prod,集合中每一个商品都有一个最晚销售时间,每一个产品都需要一个单独的单位时间销售(即两件商品不能同时销售),一个销售计划是一个有序子集Sell,Sell≤Prod,根据子集中的顺序,每一个商品都能在规定时间前销售出去。一个销售计划的利润则为Sell中的所有商品的利润和。

比如,如果Prod={a,b,c,d},(pa,da)=(50,2),(pb,db)=(10,1),(pc,dc)=(20,2), (pd,dd)=(30,1),其中pi表示商品i的价值,di表示商品i的最晚销售时间。比如一个销售计划Sell={d,a},d在0开始1时刻结束销售,a在1开始2时刻结束销售,所有商品都在规定时间前完成了销售,其利润为80,其他销售计划如表8.1所示。

 

表8.1

计划表

利润

{a}

50

{b}

10

{c}

20

{d}

30

{b,a}

60

{a,c}

70

{c,a}

70

{b,c}

30

{d,a}

80

{d,c}

50

 

写一个程序,来计算一个Prod的最大利润销售计划是多少利润。

【输入格式】

一组数据以一个整数n(0≤n≤10 000)开始,接下来有n对pi,di(1≤pi≤10 000,1≤di≤10 000),数与数之间有空格隔开。

【输出格式】

每组数据一行,输出最大利润是多少。

【输入样例】

50 2 

10 1  

20 2  

30 1

 

20 1  

2 1  

10 3 

100 2  

8 2

5 20 

50 10

【输出样例】

80

185