题目描述见链接 .
分数规划,
二分出答案 , 要满足 .
由于题目有总重量不小于 的限制, 所以不能直接贪心选,
考虑 背包, 设 表示总重量为 所能获得的最大值, 由于 较小, 而 比较大,
所以考虑将 全部存在 中, 做 背包 即可 .
#include<bits/stdc++.h>
#define reg register
const int maxn = 1005;
const double inf = 1e10;
const double eps = 1e-9;
int N;
int W;
int w[maxn];
int t[maxn];
double F[maxn];
bool check(double mid){
for(reg int i = 1; i <= W; i ++) F[i] = -inf;
F[0] = 0;
for(reg int i = 1; i <= N; i ++)
for(reg int j = W; j >= 0; j --){
double &tmp = F[std::min(W, j+w[i])];
tmp = std::max(tmp, F[j] + 1.0*t[i] - 1.0*mid*w[i]);
}
return F[W] >= 0;
}
int main(){
scanf("%d%d", &N, &W);
double l = 0, r = 0;
for(reg int i = 1; i <= N; i ++) scanf("%d%d", &w[i], &t[i]), r += t[i];
double Ans = 0;
while(r-l > eps){
double mid = (l+r)/2;
if(check(mid)) Ans = std::max(Ans, mid), l = mid + eps;
else r = mid - eps;
}
printf("%d
", (int)(Ans*1000));
return 0;
}