题目链接：http://poj.org/problem?id=2976

关于 0/1分数规划 参见 这篇博客

实现代码如下：

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cmath>

using namespace std;

const int maxn = 1010;

const double eps = 1e-4;

int n, k;

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

inline bool cmp(double a, double b) { return a > b; }

bool check(double x) {

    for (int i = 0; i < n; i ++) c[i] = a[i] - x * b[i];

    sort(c, c+n, cmp);

    double tmp = 0;

    for (int i = 0; i < n-k; i ++) tmp += c[i];

    return tmp >= 0;

}

void solve() {

    double L = 0, R = 1, res;

    while (R - L > eps) {

        double mid = (L + R) / 2.0;

        if (check(mid)) {

            res = mid;

            L = mid;

        }

        else

            R = mid;

    }

    printf("%.0f\n", res * 100);

}

int main() {

    while ( ~scanf("%d%d", &n, &k) && n ) {

        for (int i = 0; i < n; i ++) scanf("%lf", a+i);

        for (int i = 0; i < n; i ++) scanf("%lf", b+i);

        solve();

    }

    return 0;

}