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;
}