01分数规划

原理

见《进阶指南》第185页。

模板题

AcWing-234-放弃测试

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
const double eps = 1e-6;
int n, k;
int a[N], b[N];
double y[N];

bool cmp (const double& a, const double& b) {
    return a > b;
}
bool check (double val) {
    for (int i = 1; i <= n; ++ i)
        y[i] = a[i] - val * b[i];
    sort(y + 1, y + n + 1, cmp);
    double sum = 0;
    for (int i = 1; i <= n - k; ++ i) sum += y[i];
    return sum >= 0;
}

int main () {
    while (cin >> n >> k && n) {
        for (int i = 1; i <= n; ++ i) cin >> a[i];
        for (int i = 1; i <= n; ++ i) cin >> b[i];

        double l = 0, r = 1;
        while (r - l > eps) {
            double mid = (l + r) / 2;
            if (check(mid) == true)
                l = mid;
            else
                r = mid;
        }
        printf("%.0lf\n", 100 * l);
    }
    return 0;
}