nyoj914Yougth的最大化(二分搜索 + 贪心)
2024-10-17 07:58:15
Yougth的最大化
时间限制:1000 ms | 内存限制:65535 KB
难度:4
描述
Yougth现在有n个物品的重量和价值分别是Wi和Vi,你能帮他从中选出k个物品使得单位重量的价值最大吗?
输入
有多组测试数据
每组测试数据第一行有两个数n和k,接下来一行有n个数Wi和Vi。
(1<=k=n<=10000) (1<=Wi,Vi<=1000000)
输出
输出使得单位价值的最大值。(保留两位小数)
样例输入
3 2
2 2
5 3
2 1
样例输出
0.75
来源
Yougth
题解:
Yougth的最大化
这道题目是一道0-1分数规划求最优值。
方法是一个二分搜索+贪心的题目。
出这道题目就是告诉大家二分不仅可以查找,还可以搜索一个更优值。
要使得单位重量的价值最大,则其最大不超过单个中最大的单位重量的价值,最小当然不小于0.
那么我们就这一在0–最大单位重量的价值中间找一个值ans,使得ans为满足题目条件的最大值。如果满足条件,则可以找更大的。设置一个条件。既二分搜索、
从n个物品中找k个使得k个的价值和/质量和>=ans
为了使得ans尽可能的大,那么这里就要贪心选择。
代码详见:
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = ;
int w[N],v[N];
double y[N];
int n,c;
int chack(double x)
{
for(int i=;i<n;i++)
{
y[i]=v[i]-x*w[i];
}
sort(y,y+n);
double sum=;
for(int i=;i<c;i++)
{
sum+=y[n-i-];
}
return sum>=;
}
double reaerch(double enf)
{
double l=,r=enf,mid;
for(int i=;i<;i++)
{
mid=(l+r)/;
if(chack(mid))
l=mid;
else
r=mid;
}
return l;
}
int main()
{
while(~scanf("%d%d",&n,&c))
{
double ma=;
for(int i=;i<n;i++){
scanf("%d%d",&w[i],&v[i]);
double cmp=v[i]/w[i];
if(cmp>ma)
ma=cmp;
}
printf("%.2lf\n",reaerch(ma));
}
return ;
}
最新文章
- iOS 电话在后台运行时,我的启动图片被压缩
- 使用Apache ab进行压力测试(参数说明)
- Sublime Text生成html标签快捷键
- 序列化和反序列化(C#)
- windows中java读目录空格变成%20 处理方法
- gridControl 部分属性
- 9.并发包非阻塞队列ConcurrentLinkedQueue
- C#调用AForge实现摄像头录像
- Android 4.4以上使用HttpURLConnection底层使用OkHttp实现的源码分析
- AndroidStudio Frameworks detected: Android framework is detected in the project Configure
- Java中static关键字和final关键字
- WAMP中的MySQL设置用户、密码 及 phpmyadmin的配置
- VMware下Debian开发环境部署之常见问题记录
- react-踩坑记录——iconfont
- 高速公路 [HAOI2012] [线段树]
- 禁止WORDPRESS站内搜索的方法
- HAProxy 日志输出及配置
- Qt中的主窗口之菜单栏
- mongodb操作技巧
- STM32 Timer Clock sources -- External Clock Both Edge