[SPOJ699]巨大的背包

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file hugeknapsack.in Output file hugeknapsack.out

【题目描述】

我们的国王赢得了一场血腥的战争,因此现在整片大陆都是我们的了。这片大陆的特殊之处在于这里有许多美丽的纯金雕像。国王希望往他的宫殿里带回尽可能多的黄金。我们已经发现了那里有N种雕像,并且——不可思议的——每种雕像都有无数个。每一座第i种雕像的重量为W[i]个单位,并且占据V[i]个单位的体积。国王希望最大化他带回宫殿的金子总数。我们可以我们可以使用S个袋子来完成这一目标,每个的容量都是Y。所有的袋子都独立地装入纯金雕像,不能把雕像切开。不过,可以把两个袋子缝在一起,需要消耗C个单位的黄金。把三个袋子缝在一起需要消耗2*C,因为这需要两次缝合,以此类推。你的任务是找出国王最多可以获得多少金子,也就是说,带回去金子的总重量减去缝合袋子的花费。

【输入格式】

输入包含多组数据。

输入文件的第一行有一个整数T,即数据组数。

接下来是T组数据。

每组数据格式如下:

第一行:N S Y C

接下来有N行,每行含两个整数W[i]和V[i]。

【输出格式】

输出一个整数,即最多能获得多少金子。

【样例输入】

2

2 5 3 1

1 2

5 7

2 5 3 1

1 2

7 5

【样例输出】

6

17

【提示】

1<=S<=1000

1<=Y<=1000000000

1<=N<=1000

1<=W[i]<=100

1<=V[i]<=18

输出不超过64位带符号整数范围。

1<=T<=20

所有的W[i]和V[i]是素数或1.

【来源】

SPOJ 699 Huge Knap Sack

ByteCode 2006