洛谷4377（01分数规划）

二分答案，内部01背包一下重量大于等于W的最大价值是否大于等于0了。

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

typedef long long ll;
const int maxn = 255, maxw = 1e3 + 5;
const ll INF = 1e18;

int N, W;
int w[maxn], t[maxn];

bool ok(int mid) {
    ll f[maxw];
    f[0] = 0LL;
    for (int i = 1; i <= W; i++)    f[i] = -INF;

    for (int i = 1; i <= N; i++)
        for (int j = W; ~j; j--)
            if (f[j] > -INF) {
                int k = min(W, j + w[i]);
                f[k] = max(f[k], f[j] + t[i] - (ll)w[i] * mid);
            }
    return f[W] >= 0;
}

int main() {
    scanf("%d %d", &N, &W);
    for (int i = 1; i <= N; i++)
        scanf("%d %d", &w[i], &t[i]), t[i] *= 1000;

    int l = 0, r = 1e6, ans;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (ok(mid))    l = mid + 1, ans = mid;
        else    r = mid - 1;
    }
    return !printf("%d\n", ans);
}

洛谷4377（01分数规划）

原文：https://www.cnblogs.com/AlphaWA/p/10799426.html