0%

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*b_i$ 排序取最大的 $k$ 个判断即可

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

nth_element(),复杂度 $\mathcal 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()

代码

二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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;
}

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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;
}