Description：

$n$ 个物品，选出一些物品第一个属性和 $/$ 第二个属性和最大且第二个属性和 $\ge W$ ，

$1\le n \le 250,1\le W\le 1000$

Solution：

$01$ 分数规划，反正 $n$ 和 $W$ 都很小可以背包表示和为 $k$ 时的最大价值，把每个物品的价值换成 $t-mid\times w$ ，那么如果和 $\ge W$ 且值为正就说明存在一种合法方案， $\ge W$ 的方案已经满足题意所以等价，可以用取 $\min$ 的技巧把这些状态合成一个状态。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,w;

#define MAXN 251

struct cow

{

	int w,t;

	double val;

}c[MAXN];

const double eps = 1e-6;

#define MAXW 1010

double f[MAXW];

bool check(double k)

{

	for(int i = 1;i <= n;++i)c[i].val = c[i].t - k * c[i].w;

	for(int i = 1;i <= w;++i)f[i] = -10000000000.0;

	f[0] = 0.0;

	for(int i = 1;i <= n;++i)

	{

		for(int j = w;j >= 0;--j)

		{

			if(j + c[i].w >= w && f[j] + c[i].val >= 0)return true;

			f[min(w,j + c[i].w)] = max(f[min(w,j + c[i].w)],f[j] + c[i].val);

		}

	}

	return false;

}

int main()

{

	scanf("%d%d",&n,&w);

	for(int i = 1;i <= n;++i)scanf("%d%d",&c[i].w,&c[i].t);

	double l = 0.0,r = 1000000.0,mid;

	while(r - l > eps)

	{

		mid = (l + r) / 2;

		if(check(mid))l = mid;

		else r = mid;

	}

	printf("%d\n",(int)(l * 1000.0));

	return 0;

}