Menu
Article

01分数规划入门

NodeKey

NodeKey

• 3 min read

很早就想学的东西了……但是要学的实在是太多了……

01分数规划是分数规划中最简单的，所谓01，就是对于每一件物品，他都是不同的，你只有取或者不取两种选择，没有在数量上太多的选择。就像01背包一样。
01分数规划 虽然考察的不多，套路也比较死，但是多校的时候着实出现过。记得应该是cls的那一场，记得是01分数规划的新操作……

01分数规划是用来解决取舍导致的比例最值问题。解决该问题的方法有两种。
一种是二分，另一种是迭代，迭代法也称 Dinkelbach 算法。
二分法基于验证，迭代法基于直接计算，一般来说迭代法会更快一些。
两者写起来都非常简单。
入门资料推荐。具体思路不再细说。
入门题在这里。

入门资料中谈到，如果对于题目改成最小化，那么就尽量少选，不是很理解他的说法。
就我看来，把分子分母倒一下就转换过来了。

题意：
最裸的01分数规划，要你从 n 个中挑出 k 个使得比例最大。

就图片来说就是要你求这样的结果，当然是选取 k 个。

思路：
验证板子的题，因为它的限制只有一个，没什么好说的。看了上面的入门资料就很好理解的。
01分数规划可怕的是大量的限制。考虑的真的是脑壳疼。

这里贴出两种解法的代码。

Dinkelbach

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <cmath>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const double eps = 1e-5;
const int maxn = 1e3 + 5;
int n, k;

double a[maxn], b[maxn], d[maxn];
int id[maxn];

bool cmp(int a, int b) { return d[a] > d[b]; }

double Dinkelbach()
{
    double ans = 0, L, x, y;
    do {
        L = ans, x = 0, y = 0;
        each(i, n) d[i] = a[i] - L * b[i];
        each(i, n) id[i] = i;
        sort(id, id + n, cmp);
        each(i, n - k) x += a[id[i]], y += b[id[i]];
        ans = 1.0 * x / y;
    } while (fabs(ans - L) > eps);
    return ans;
}

int main()
{
    while (scanf("%d %d", &n, &k) != EOF && n + k) {
        each(i, n) scanf("%lf", a + i);
        each(i, n) scanf("%lf", b + i);
        printf("%.0f\n", Dinkelbach() * 100);
    }
    return 0;
}

二分

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const double eps = 1e-5;
const int maxn = 1e3 + 5;
int n, k;

double a[maxn], b[maxn], d[maxn];

bool judge(double key)
{
    each(i, n) d[i] = a[i] - key * b[i];
    sort(d, d + n, greater<double>());
    double sum = 0;
    each(i, n - k) sum += d[i];
    return sum - eps > 0;
}

int main()
{
    while (scanf("%d %d", &n, &k) != EOF && n + k) {
        each(i, n) scanf("%lf", a + i);
        each(i, n) scanf("%lf", b + i);
        double l = 0, r = 1e12, mid;
        while (r - l > eps) {
            mid = (l + r) / 2;
            if (judge(mid))
                l = mid;
            else
                r = mid - eps;
        }
        printf("%.0f\n", l * 100);
    }
    return 0;
}
Share