【0/1分数规划+01背包】Talent Show HYSBZ - 5281 达牛秀

Time Limit: 10 Sec
Memory Limit: 128 MB
Description
FarmerJohn要带着他的N头奶牛，方便起见编号为1…N，到农业展览会上去，参加每年的达牛秀！他的第i头奶牛重
量为wi，才艺水平为ti，两者都是整数。在到达时，FarmerJohn就被今年达牛秀的新规则吓到了：
（一）参加比赛的一组奶牛必须总重量至少为W
（这是为了确保是强大的队伍在比赛，而不仅是强大的某头奶牛），并且
（二）总才艺值与总重量的比值最大的一组获得胜利。
FJ注意到他的所有奶牛的总重量不小于W，所以他能够派出符合规则（一）的队伍。帮助他确定这样的队伍中能够
达到的最佳的才艺与重量的比值。

Input
输入的第一行包含N和W。下面N行，每行用两个整数wi和ti描述了一头奶牛。
1≤N≤250
1≤W≤1000
1≤wi≤10^6
1≤ti≤10^3

Output
请求出Farmer用一组总重量最少为W的奶牛最大可能达到的总才艺值与总重量的比值。
如果你的答案是A，输出1000A向下取整的值，以使得输出是整数
（当问题中的数不是一个整数的时候，向下取整操作在向下舍入到整数的时候去除所有小数部分）。

思路

看到选择牛，每个牛对应weight和talent，使其总合比值最大化，立马想到0/1分数规划。
使其总重量大于等于一定值，可以把变形后的0/1分数规划式子作为牛的价值，然后和牛的重量一起做01背包即可

#include<cstdio>
#include<algorithm>
using namespace std;
#define eps 1e-7
long long weight[260], talent[260];
double temp[1005];
double dp[1005];
long long n, tw;
bool check(double x) {
   
	for (int i =1; i <= n; i++) {
   
		temp[i] = talent[i] - x * weight[i];
	}
	for (int i = 1; i <= tw+1; i++) {
   
		dp[i] = -1e18;
	}
	for (int i = 1; i <= n; i++) {
   
		for (int j = tw + 1; j >= 0; j--) {
   
			dp[min(tw + 1, j + weight[i])] = max(dp[min(tw + 1, j + weight[i])], dp[j] + temp[i]);
		}
	}
	return dp[tw] >= eps || dp[tw + 1] >= eps;
}
int main(void) {
   
	scanf("%lld%lld", &n, &tw);
	double left = 0,right = 0;
	for (int i = 1; i <= n; i++) {
   
		scanf("%lld%lld", &weight[i], &talent[i]);
		right += talent[i];
	}
	while (left + eps <= right) {
   
		double mid = (left + right) / 2.0;
		if (check(mid)) {
   
			left = mid;
		}
		else {
   
			right = mid;
		}
	}
	printf("%d\n", (int)(left * 1000));
	return 0;
}