01分数规划

问题

有 $n$ 个物品，每个物品有两个属性 $a_i$ 和 $b_i$，需要选出 $k$ 个，设选出的编号集合是 $S$。

最大化

$$\frac{\sum _{i\in S}{a}_i}{\sum _{i\in S}{b}_i}$$

保留一定精度。

二分

这个问题是可以二分的，考虑二分一个答案 $ans$，条件是

$$\frac{\sum _{i\in S}{a}_i}{\sum _{i\in S}{b}_i}\ge ans$$

可以转化为

$$\sum _{i\in S}{a}_i-ans\sum _{i\in S}{b}_i\ge 0$$

这样只需要按照 $a_i-ans\ast b_i$ 排序取最大的 $k$ 个判断即可。

直接使用 sort()，令 $w$ 表示 $\frac{\text{值域}}{\text{精度}}$，复杂度 $O(n\log n\log w)$。

用 nth_element()，复杂度 $O(n\log w)$。

问题有其他变种，大概挺simple，二分基本上就好了。

迭代

不知道这复杂度对不对，好像正确性也不知道，反正跑得快。

先令 $ans=0$，每次用相同的方法，可以求出一个 $\frac{\sum _{i\in S}{a}_i}{\sum _{i\in S}{b}_i}$，显然这也是一个合法的答案，并且肯定更优。

一直迭代直到增加量很小时结束。

例题

LOJ #149. 01分数规划

模板

迭代目前跑得最快。

二分的代码的写法大概是因为寻址不连续，没有写 struct 一起 nth_element() 快。

代码

二分

#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>

using namespace std;
#define ll long long

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig=false, c=read(); !isdigit(c); c=read()) {
		if (c == '-') iosig=true;
		if (c == -1) return;
	}
	for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
	if (iosig) x=-x;
}

const int N = 100005;
int n, k, a[N], b[N], g[N];
double f[N];
inline bool cmp(int x, int y){ return f[x]>f[y];}
inline double check(double x){
	for(int i=1; i<=n; ++i) f[i]=a[i]-b[i]*x, g[i]=i;
	nth_element(g+1, g+k+1, g+n+1, cmp);
	ll sa=0, sb=0;
	for(int i=1; i<=k; ++i) sa+=a[g[i]], sb+=b[g[i]];
	return (double)sa/sb;
}
int main() {
	read(n), read(k);
	for(int i=1; i<=n; ++i) read(a[i]);
	for(int i=1; i<=n; ++i) read(b[i]);
	double l=0, r=1e6, ans=0;
	while(r-l>1e-7){
		double mid=(l+r)/2;
		if(check(mid)>=mid) ans=mid, l=mid; else r=mid;
	}
	return printf("%.4f", ans), 0;
}

迭代

#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>

using namespace std;
#define ll long long

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig=false, c=read(); !isdigit(c); c=read()) {
		if (c == '-') iosig=true;
		if (c == -1) return;
	}
	for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
	if (iosig) x=-x;
}

const int N = 100005;
int n, k;
struct item{
	int a, b;
	double f;
	inline bool operator <(const item &rhs)const{ return f>rhs.f;}
} a[N];
inline double check(double x){
	for(int i=1; i<=n; ++i) a[i].f=a[i].a-a[i].b*x;
	nth_element(a+1, a+k+1, a+n+1);
	ll sa=0, sb=0;
	for(int i=1; i<=k; ++i) sa+=a[i].a, sb+=a[i].b;
	return (double)sa/sb;
}
int main() {
	read(n), read(k);
	for(int i=1; i<=n; ++i) read(a[i].a);
	for(int i=1; i<=n; ++i) read(a[i].b);
	ll sa=0, sb=0;
	for(int i=1; i<=k; ++i) sa+=a[i].a, sb+=a[i].b;
	double ans=(double)sa/sb, last;
	do ans=check(last=ans); while(ans-last>1e-6);
	return printf("%.4f", ans), 0;
}