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

Output

Input

Output

Input

Output

Input

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$ 。

1001. 栈的实现 1002. 铁路调度 1003. 数据生成器 1004. 队列的实现 1005. 座位分配 1006. 车厢调度 1007. Max Element 1008. 最小的n个和 1009. 数据整理 1010. 约瑟夫环问题 1011. 链表去重 1012. n皇后问题 1013. 迷宫搜索 1014. 构造字典序最小字符串 1015. 任务调度 1016. 快速排序 1017. 逆序对 1018. 最大最小问题 1019. 层次遍历 1020. 医疗队列 1021. 数独问题 1022. 终极背包问题 1023. 终极混合背包问题 1024. 分割回文串 1025. 树的直径 1026. 路径差 1027. 旅行商问题 1028. 数的变换 1029. 单峰序列 1030. 高级并查集 1031. 传送门（一） 1032. 传送门（三） 1033. 一元多项式乘法 1034. 表达式 1035. 恢复古诗 1036. 代码查重 1037. Take a party 1038. 小强的烦恼 1039. 树的双亲存储法 1040. A Knight's Journey 1041. 华师大卫星照片 1042. Can you do DFS? 1043. 斐波那契数列和 1044. 说出来可能不信这是排序题 1045. 最大的子串 1046. 最小等待时间 1047. 判断两个数是否相等 1048. 电话送报 1049. 简单排序题 1050. Ants 1051. 付款问题 1052. 数塔 1053. 最长连续公共子序列 1054. 整数的拆分 1055. 完全加括号的矩阵连乘积 1056. 装箱问题 1057. 统计字符串个数 1058. 子集和问题 1059. 区间覆盖 1060. 0-1背包问题 1061. 放书 1062. 经典的猜数游戏 1063. 最近点对 1064. 双人旋转赛车 1065. Hanoi Tower II 1066. Hanoi Tower III 1067. Hanoi Tower IV 1068. 奇异收缩的剪影

数据结构与算法专题题库

输入格式

输出格式

样例

提示

题目列表

服务

开源

关于我们