大家好，又见面了，我是全栈君。
- 题目地址：http://poj.org/problem?
- 题目大意：给你n个物品的a值和b值，要你从中丢掉k个（或者说选择n-k个）物品，使得剩下的物品的
![[POJ 2976]Dropping tests(0-1分数规划)](http://poj.org/images/2976_1.gif)
![[POJ 2976]Dropping tests(0-1分数规划)](http://javaforall.cn/wp-content/themes/justnews/themer/assets/images/lazy.png)
最大 - 题目思路(以下思路转自http://blog.csdn.net/neofung/article/details/7649603)：
我们能够看看例如以下推导
![[POJ 2976]Dropping tests(0-1分数规划)](http://my.csdn.net/uploads/201206/10/1339295491_9968.gif)
题目就变成了二分检索r
-
代码：
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> #include <cmath> #define MAXN 1010 #define EPS (1e-6) #define INF 0x3f3f3f3f using namespace std; double w[MAXN],v[MAXN]; int n,k; double value[MAXN]; bool check(double x) //推断平均值x是否可取 { double sum=0; for(int i=1;i<=n;i++) value[i]=v[i]-x*w[i]; sort(value+1,value+n+1); //贪心排序，从大到小选取k个value[i]，且这k个value的和必须不小于0 for(int i=n;i>=n-k+1;i--) sum+=value[i]; return sum>=0; } int main() { while(scanf("%d%d",&n,&k)!=EOF&&!(n==0&&k==0)) { k=n-k; for(int i=1;i<=n;i++) scanf("%lf",&v[i]); for(int i=1;i<=n;i++) scanf("%lf",&w[i]); double lowerBound=0,upperBound=INF; //二分这个平均值 while(fabs(upperBound-lowerBound)>EPS) { double mid=(lowerBound+upperBound)/2; if(check(mid)) lowerBound=mid; else upperBound=mid; } printf("%.f\n",100*upperBound); } return 0; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/115619.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
