部分背包
测试数据来自 system/1125
作业已超过截止时间,您无法递交本题目。
时间限制:1秒 内存限制:256M
【问题描述】
有 \(n\) 个物品,物品i的体积为 \(v[i]\),价值为 \(p[i]\)。现有容量为 \(C\) 的背包,最多能装载 \(C\) 的体积,请计算怎样装入才能使背包中装载的的物品价值最高。
注意:物品可部分装载,如果商品 \(i\) 只装入 \(x\) 部分,则价值为:\((p[i]*x/v[i])\)。
【输入格式】
第 1 行是 \(n\) 和 \(C\);
第 2 行有 \(n\) 个整数,表示物品的体积 \(v[i]\);
第 3 行有 \(n\) 个整数,表示物品的价值 \(p[i]\)。
【输出格式】
输出一个小数,表示装入物品的最大价值,保留2位小数。
【输入输出样例】
Input
6 10
1 5 3 2 4 6
1 6 2 3 5 5
Output
12.80
【数据规模与约定】
\(0<n<=50000\)
\(0<C,v[i],p[i]<=10^9\)
【来源】
Mr.he