数据结构与算法专题题库

1022. 终极背包问题

单点时限: 5.0 sec

内存限制: 512 MB

给你一个背包,但是背包只能装载总重为$W$的物品,请问如何选择物品$T$装入背包,使得背包中的物品价值最大。

其中物品有以下几类:

  • 01物品:表示为$w_i,v_i$,其中$w_i$为质量,$v_i$为价值,这类商品要么选择,要么不选择。
  • 有限01物品:表示为$w_i,v_i,c_i$,其中$w_i$为质量,$v_i$为价值,$c_i$为最大数量,这类商品最多选择$c_i$件。
  • 无限01物品:表示为$w_i,v_i$,其中$w_i$为质量,$v_i$为价值,这类商品可以选择任意数量。
  • 分数物品:表示为$w_i,v_i$,其中$w_i$为质量,$v_i$为价值,这类商品可以选择任意数量,并且可以选择其中任意一部分,假设选择质量$w$,满足$0 \leq w \leq w_i$,则获得的价值为$v_i*\frac{w}{w_i}$。

在这个问题中你需要考虑这4类商品,并且这4类商品只会出现一种

输入格式

第一行为四个数$a,b,c,d,T$,表示$4$类商品的数量和背包的质量。

接下来$a$行,每行两个数$w_i,v_i$表示第$i$件01物品的信息。
接下来$b$行,每行三个数$w_i,v_i,c_i$表示第$i$件有限01物品的信息。
接下来$c$行,每行两个数$w_i,v_i$表示第$i$件无限01物品的信息。
接下来$d$行,每行两个数$w_i,v_i$表示第$i$件分数物品的信息。

数据范围:
$(a+c) * T + \sum_{i=1}^{b} c_i * T + d \log d \leq 10^7 $

$v_i \leq 10^9$

$T \leq 10^3$

$w_i \leq T$

$a+b+c+d \leq 10^4$

$ (a \geq 1) + (b \geq 1) + (c \geq 1) + (d \geq 1) == 1$

输出格式

一个数表示最大价值$V$,答案可能是小数,精确到小数点后6位。

样例

Input
5 0 0 0 10
2 6
2 3
6 5
5 4
4 6
Output
15
Input
0 5 0 0 10
2 6 1
2 3 2
6 5 3
5 4 2
4 6 1
Output
18
Input
0 0 5 0 10
2 6
2 3
6 5
5 4
4 6
Output
30
Input
0 0 0 5 10
2 6
2 3
6 5
5 4
4 6
Output
16.6666666667

提示

题目是10.2的简化版,能够通过10.2的程序也可以通过10.1。

数据说明;

前10组测试数据满足$a \geq 1$。
之后10组测试数据满足$b \geq 1$。
再之后10组测试数据满足$c \geq 1$。
最后10组测试数据满足$d \geq 1$。

不限期开放

题目列表