luoguP4377 01分数规划 背包dp

emmm……看到题面“总才艺值与总体重的比值最大”，那么这个就是01分数规划问题了。
现在详细讲一讲如何解决这类问题。
先看简单一点的题：
有 n 个物品，有属性值 ai,bi要求选出至多 k 个物品，使得sum(ai) / sum(bi)尽可能大。
我们要首先二分答案 x，若 sum(ai) / sum(bi) ≥x 则说明答案可以更大。
稍微变形一下：sum(a[i]) >= sum(b[i]) * x;
继续：sum(a[i] - b[i] * x) >= x
我们发现 i 对答案的贡献是个常数 ai-bi了！
由于至多选 k 个物品，我们可以贪心，将 ai-bix从大到小排序，然后选出前 kk 个前缀和的最大值。如果是非负数那么答案就可以变得更大。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 5;
const ll inf = 1e18;
ll w[maxn], t[maxn];
ll dp[maxn];
int N, W;
ll check(ll mid) {
    for (int i = 0; i < maxn; i++) {
        dp[i] = -inf;
    }
    dp[0] = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = W; j >= 0; j--) {
            if (dp[j] != -inf) {
                int jj = j + w[i];
                jj = min(jj, W);
                dp[jj] = max(dp[jj], dp[j] + t[i] - (ll) w[i] * mid);
            }
        }
    }
    return dp[W] >= 0;
}
ll solve() {
    ll l = 0, r = 1e7;
    while (l <= r) {
        ll mid = (l + r) / 2;
        if (check(mid)) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return l - 1;
}
int main() {
    cin >> N >> W;
    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> t[i];
        t[i] *= 1000;
    }
    cout << solve() << endl;
    return 0;
}