poj2976(01分数规划)

本文主要是介绍poj2976(01分数规划)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：点击打开链接

题意；有n场考试，给出每场答对的题数a和这场一共有几道题b，求去掉k场考试后，公式.的最大值

代码：

#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int n,m;
double a[1005],b[1005],c[1005];
int judge(double mid){int i;double ans=0;for(i=1;i<=n;i++)c[i]=a[i]-mid*b[i];sort(c+1,c+n+1);for(i=n;i>m;i--)ans+=c[i];if(ans>=0)return 1;return 0;
}
int main(){                                     //01分数规划，下面博客讲的特别详细int i,j;                                    //http://www.cnblogs.com/perseawe/archive/2012/05/03/01fsgh.htmldouble l,r,mid;while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){for(i=1;i<=n;i++)scanf("%lf",&a[i]);for(i=1;i<=n;i++)scanf("%lf",&b[i]);l=0,r=INF*1.0;for(i=1;i<=100;i++){mid=(l+r)/2;if(judge(mid))l=mid;elser=mid;}printf("%.0lf\n",l*100);}return 0;
}

这篇关于poj2976(01分数规划)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---