01分数规划

acm

01 分数规划

A - Dropping testsPOJ - 2976

给出n个ai,bi,，求最大的$ \frac{\sum a_i}{\sum b_i} $，删除k对，方案一：二分最大的比值，可以考虑每次排序都选择x.a - (p * x.b)大的前n-k个，这样计算出的答案看能否成立。

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
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
const int maxn = 1e3+10;
using namespace std;
int n,k;
struct node{
    int a,b;
}val[maxn];
double p;
int cmp(node x, node y){
    return x.a - (p * x.b) > y.a - (p * y.b);
}

bool check(double mid){
    p = mid;
    sort(val, val + n, cmp);
    double total_a = 0,total_b = 0;
    for(int i = 0; i < n - k; i++){
        total_a += val[i].a;
        total_b += val[i].b;
    }
    return (total_a/total_b) > mid;
}

int main(){
    while(~scanf("%d%d",&n,&k) && n){
        for(int i = 0; i < n; i++){
            scanf("%d",&val[i].a);
        }
        for(int i = 0; i < n; i++){
            scanf("%d",&val[i].b);
        }

        double l = 0, r = 1;
        double mid;
        for(int i = 0; i < 200; i++){
            mid = (l+r)/2;
            if(check(mid)){
                l = mid;
            }else{
                r = mid;
            }
        }
        printf("%d\n",(int)round(mid*100));
    }
    return 0;
}

方案二：

Dinkelbach算法

伪代码：

1
2
3
4
5
6
7
8
9
10
Algorithm Dinkelbach(double L)
{
    for i=1 ~n
       g[i]= a[i]-L*b[i]
       vis[i]=false //开始时均未被选择
    for i=1 ~k
       for i=1 ~n
          check each to choose the best ans
       vis[index]=1;//标记已经选择过的产品
}

实现：

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
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
const int maxn = 1e3+10;
using namespace std;
int n,k;
struct node{
    int a,b;
}val[maxn];
double p;
int cmp(node x, node y){
    return x.a - (p * x.b) > y.a - (p * y.b);
}

double check(double mid){
    p = mid;
    sort(val, val + n, cmp);
    double total_a = 0,total_b = 0;
    for(int i = 0; i < n - k; i++){
        total_a += val[i].a;
        total_b += val[i].b;
    }
    return (total_a/total_b);
}

int main(){
    while(~scanf("%d%d",&n,&k) && n){
        for(int i = 0; i < n; i++){
            scanf("%d",&val[i].a);
        }
        for(int i = 0; i < n; i++){
            scanf("%d",&val[i].b);
        }

        double l = 0, r;
        for(int i = 0; i < 10; i++){
            r = check(l);
            l = r;
        }
        printf("%d\n",(int)round(l*100));
    }
    return 0;
}

这个方法迭代很快就能得到。还可以考虑一种n^2暴力的方案，每次寻找一个最优解。

B - Sightseeing CowsPOJ - 3621

求最优比例生成环，利用spfa去判负环，松弛操作改成+ mid * edge[i].w - w[u];前面一个w是cost,是本来的分母，后面的一个w[u]是分子；这里让他减小就可以判到负环。这里是二分实现，想要用Dinkelbach实现请看下面一道题

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
const int maxn = 1e3+10;
using namespace std;
struct edge{
    int v,w,next;
}edge[maxn*5];
int cnt,head[maxn];
void add(int u, int v, int w){
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
int n,m;
int w[maxn];
double dis[maxn];
bool vis[maxn];
int rak[maxn];

bool spfa(double mid){
    queue<int> q;
    memset(vis,0,sizeof vis);
    memset(rak,0,sizeof rak);
    for(int i = 0; i <= n; i++){
        dis[i] = 1e15;
    }
    q.push(1);
    dis[1] = 0;
    vis[1] = 1;
    rak[1] ++;
    while(!q.empty()){
        int u = q.front();q.pop();
        vis[u] = 0;
        for(int i = head[u]; i != -1; i = edge[i].next){
            int v = edge[i].v;
            int y = edge[i].w;
            if(dis[u] + mid * y - w[u] < dis[v]){
                dis[v] = dis[u] + mid * y - w[u];
                if(!vis[v]){
                    q.push(v);
                    vis[v] = 1;
                    rak[v] ++;
                    if(rak[v]>=n)
                        return 1;
                }
            }
        }
    }
    return 0;
}

int main(){
    cnt = 0;
    memset(head, -1, sizeof head);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d",&w[i]);
    }
    int a,b,c;
    for(int i = 1; i <= m; i++){
        scanf("%d%d%d",&a,&b,&c);
        add(a, b, c);
    }
    double l = 0, r = 1e4, mid;
    for(int i = 0; i < 30; i++){
        mid = (l+r)/2;
        if(spfa(mid))
            l = mid;
        else r = mid;
    }
    printf("%.2f\n",l);
    return 0;
}

C - Desert KingPOJ - 2728

这题是最优比例生成树，我们利用prim，每次更新所有节点到首届点的距离。松弛操作还是利用 cost[i][j] - l*dis[i][j]， 然后去找一下最小生成树，计算一下就是新的答案。

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
const int maxn = 1e3 + 5;
using namespace std;

int n;
double dis[maxn][maxn], d[maxn], w[maxn][maxn];
int cost[maxn][maxn], pre[maxn];
bool vis[maxn];

struct Point{
    int x,y,z;
    void read(){
        scanf("%d%d%d",&x,&y,&z);
    }
    double dis(const Point &p){
        return sqrt((x-p.x)*(x-p.x)*1.0+(y-p.y)*(y-p.y));
    }
    int cost(const Point &p){
        return abs(z - p.z);
    }
}g[maxn];
//找负环
double prim(){
    if(n == 1){
        return 0;
    }
    memset(vis, 0 ,sizeof vis);
    memset(d, 127 ,sizeof d);
    int u = 1, times = 0;
    double l = 0;
    int we = 0;
    while(++times < n){
        vis[u] = 1;
        for(int v = 0; v < n; v++){
            if(!vis[v] && w[u][v] < d[v]){
                d[v] = w[u][v], pre[v] = u;
            }
        }
        double minx = d[n];
        for(int v = 0; v < n; v++){
            if(!vis[v] && minx > d[v]){
                minx = d[v];
                u = v;
            }
        }
        if(minx == d[n]){
            return -1;
        }
        we += cost[pre[u]][u];
        l += dis[pre[u]][u];
    }
    return we / l;
}


void build(double l){
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            w[i][j] = w[j][i] = cost[i][j] - l*dis[i][j];
        }
    }
}

int main(){
    while(~scanf("%d",&n) && n){
        for(int i = 0; i < n; i++){
            g[i].read();
        }
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                dis[i][j] = dis[j][i] = g[i].dis(g[j]);
                cost[i][j] = cost[j][i] = g[i].cost(g[j]);
            }
        }
        double l = 0;
        for(int i = 0; i < 20; i++){
            build(l);
            l = prim();
        }
        printf("%.3f\n",l);
    }
    return 0;
}

D - Simple Distributed storage systemPOJ - 3757

首先读懂了题意然后根据题目意思递推最后发现转化成了A题。

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
#include<cstdio>
#include<iostream>
#include<algorithm>
const int maxn = 2e4+20;
using namespace std;
int n,k;
double f;
struct node{
    double p,b,c;
    double x;
}val[maxn];
double p;
bool cmp(node a, node b){
    return a.x*a.c - p*a.x < b.x*b.c - p*b.x;
}

double dink(){
    sort(val, val + n, cmp);
    double total_s=0;
    double total_b=0;
    for(int i = 0; i < k; i++){
        total_s += val[i].x*val[i].c;
        total_b += val[i].x;
    }
    return total_s/total_b;
}

int main(){
    while(~scanf("%d%d%lf",&n,&k,&f)){
        for(int i = 0; i < n; i++){
            scanf("%lf%lf%lf",&val[i].p,&val[i].b,&val[i].c);
            val[i].x = (val[i].p * val[i].b)/(val[i].p + val[i].b);
        }
        double l = 0;
        for(int i = 0; i < 10; i++){
            p = l;
            l = dink();
        }
        printf("%.4f\n",p*f);
    }
    return 0;
}

本文标题:01分数规划

文章作者:呼哧

发布时间:2017-09-08, 18:40:42

最后更新:2018-08-04, 02:45:05

原始链接:http://hu-chi.github.io/2017/09/08/acm/01分数规划/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 01 分数规划
    1. 1.1. A - Dropping testsPOJ - 2976
    2. 1.2. B - Sightseeing CowsPOJ - 3621
    3. 1.3. C - Desert KingPOJ - 2728
    4. 1.4. D - Simple Distributed storage systemPOJ - 3757
|