Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 4282 --3.最大价值
4282: 3.最大价值
警告!
题目
状态
题解(2)
题目描述
很快小明的生日到了,小明的父母为了给小明过一个开心的生日,叫小明到城里唯一的一间儿童商店购买小明喜欢的商品,商店里共有n种商品,商品i的总重量为w[i],商品i总价值为v[i],小明带了一个背包去商店,背包最多能装M的重量。其中(1 <= i <= N, 0 < w[i] < M)。现在请你编一个程序帮小明算一算:怎样装才能使背包中装入的商品价值最高(对于每种商品i可以只装该商品的一部分x[i],当然也只能获得部分的价值:(x[i]/w[i])\*v[i]。
输入
从文件beibao.in中读入数据,文件的第一行是两个正整数N和M,N表示商店共有N种商品,M表示小明背包的最大容量,接下来共有N行,每行有两个正整数w[i]和v[i]表示第i种商品的重量和第i种商品的价值。
输出
结果输出到文件beibao.out中,只有一个正整数,表示小明能获得的最大价值,结果四舍五入到小数后第二位。
样例输入输出
输入#1
复制
3 21 6 14 10 8 18 20
输出#1
复制
30.67
提示
Beibao.in 3 21 //有3种商品,背包的最大容量为21 6 14 //第1种商品的重量为6,总价值为14 10 8 //第2种商品的重量为10,总价值为8 18 20 //第3种商品的重量为18,总价值为20 Beibao.out 30.67 样例说明:第一种商品取重量为6,第三种商品取重量为15,故所得到的价值为: (14/6)\*6+(20/18)\*15=30.67 说明:N为小于等于1000的正整数,M为小于等于是1000的正整数,其余数据全部为小于100的正整数,注意结果四舍五入到小数后第二位。
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
普及-
标签
背包
点击显示
if ($pr_flag) { ?>
递交数
58
已通过
30
} ;?>
通过率
52%
时间限制
1 秒
内存限制
128 MB
来源
2008东莞初赛
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和