部分背包

测试数据来自 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

贪心算法练习题(一)

未认领
状态
已结束
题目
11
开始时间
2024-01-18 00:00
截止时间
2024-03-01 23:59
可延期
24.0 小时