题目大意就给定n个二元组(a,b)，扔掉k个二元组，使得剩下的a元素之和与b元素之和的比率最大。
关于0,1分数规划这个文章介绍的不错
01分数规划问题：给定两个数组，a[i]表示选取i的收益，b[i]表示选取i的代价。如果选取i，定义x[i]=1否则x[i]=0。每一个物品只有选或者不选两种方案，求一个选择方案使得R=sigma(a[i]*x[i])/sigma(b[i]*x[i])取得最值，即所有选择物品的总收益/总代价的值最大或是最小（一般题目都是规定好取K个1）（在下面先讨论最大值X）。
可以对目标式分析得到，必有一种取{ x[i] }的方式使sigma(a[i]*x[i])-X*sigma(b[i]*x[i])=0，其他的取{x[i]}的方式只能使sigma(a[i]*x[i])/sigma(b[i]*x[i])<X，当
sigma(a[i]*x[i])-X*sigma(b[i]*x[i])=0时,所以sigma((a[i]-X*b[i])*x[i])=0即把每一项(a[i]-X*b[i])*x[i]，从大到小排序一下，选K个，那么这K个1就确定下来了。这样就可以下手了，可以二分出答案，比X小的X0再把每一项(a[i]-X0*b[i])*x[i]排序一下，，前K大个的和一定大于0即sigma(a[i]*x[i])/sigma(b[i]*x[i])>X0，
当然同样利用这种思路，可以不用二分可以用Dinkelbach算法，即迭代法
L:=任意值; RepeatAns:=L;For I=1..X do D[i]:=A[i]-L*B[i];//根据L计算D数组检查解并记录;p:=0;q:=0;for I=每一个元素 do如果元素I在解中beginp:=p+A[i];q:=q+A[i];end;L:=p/q;//更新解 Until abs(Ans-L)<Eps; 本题代码：//204K94MS#include<cstdio>#include<iostream>#include<math.h>#include<algorithm>#define esp 1e-7using namespace std;int n,k;int v[1100],w[1100];double y[1100];bool ok(double x){for(int i=0;i<n;i++)y[i]=v[i]-x*w[i];sort(y,y+n); //从小到大排序，再反向选取double sum=0;for(int i=k;i<n;i++) sum+=y[i];return sum>=0;}int main(){while(~scanf("%d%d",&n,&k)&&(n||k)){for(int i=0;i<n;i++) scanf("%d",&v[i]);for(int i=0;i<n;i++) scanf("%d",&w[i]);double lb=0,ub=1;while(ub-lb>esp){double mid=(ub+lb)/2;if(ok(mid)) lb=mid;else ub=mid;}printf("%.f\n",ub*100); //需要四舍五入}return 0;}
接受自己的失败面，是一种成熟，更是一种睿智;
