POJ 2976 Dropping tests 01分数规划

时间:2023-11-26 14:30:44

给出n(n<=1000)个考试的成绩ai和满分bi,要求去掉k个考试成绩,使得剩下的∑ai/∑bi*100最大并输出。

典型的01分数规划

要使∑ai/∑bi最大,不妨设ans=∑ai/∑bi,则∑ai-ans*∑bi=0。

设f[ans]=∑ai-ans*∑bi,我们要求一个ans的最大值,使得存在一组解,满足f[ans]=0,而其他的任意解都有f[ans]<=0(如果f[ans]>0,说明∑ai/∑bi>ans,即还有比ans更优的解),对于∑ai/∑bi,从0~1二分枚举答案,对于每一个枚举到的答案mid,如果f[mid]的最大值>0,则说明存在更大的ans,从mid~r里边进一步找更优的解。否则从l~mid中找。

如何求f[mid]的最大值,f[ans]=∑ai-ans*∑bi=∑(ai-ans*bi)

显然如果mid确定了,那么对于每个考试,ai-mid*bi的值也就确定,那么从大到小排序,取最大的n-m个数进行累加即可。

二分答案法 94MS

 #include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<queue>
#include<string>
#include<sstream>
#define eps 1e-9
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
typedef long long LL;
int i,j,k,n,m,x,y,T,ans,big,cas,a[],b[];
bool flag;
double dp[],d[];
double run(double u)
{
double cur=;
for (int i=;i<=n;i++) d[i]=a[i]-u*b[i];
sort(d+,d++n);
for (i=m+;i<=n;i++) cur+=d[i];
return cur;
} int main()
{
while (scanf("%d%d",&n,&m),n+m)
{
for (i=;i<=n;i++) scanf("%d",&a[i]);
for (i=;i<=n;i++) scanf("%d",&b[i]);
double l=,r=;
while (r-l>eps)
{
double mid=(l+r)/;
if (run(mid)>) l=mid;
else r=mid;
}
printf("%d\n",(int)(r*+0.5));
}
return ;
}

Dinkelbach算法(牛顿迭代法) 32MS

事先随意确定一个数,然后逼近正确答案。

 #include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<queue>
#include<string>
#include<sstream>
#define eps 1e-9
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
typedef long long LL;
struct node
{
double num;
int i;
}d[];
int i,j,k,n,m,x,y,T,big,cas,a[],b[];
bool flag;
double l,ans;
LL p,q;
bool cmp(node a,node b)
{
return a.num<b.num;
}
int main()
{
while (scanf("%d%d",&n,&m),n+m)
{
for (i=;i<=n;i++) scanf("%d",&a[i]);
for (i=;i<=n;i++) scanf("%d",&b[i]);
l=;ans=;
while (fabs(l-ans)>eps)
{
ans=l;
for (i=;i<=n;i++)
{
d[i].num=a[i]*1.0-l*b[i];
d[i].i=i;
}
sort(d+,d++n,cmp);
p=q=;
for (i=m+;i<=n;i++)
{
p+=a[d[i].i];
q+=b[d[i].i];
}
l=p*1.0/q;
}
printf("%d\n",(int)(ans*+0.5));
}
return ;
}

注意Dinkelbach算法中p,q要使用long long