洛谷4377（01分数规划）

二分答案，内部01背包一下重量大于等于W的最大价值是否大于等于0了。

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;
const int maxn = 255, maxw = 1e3 + 5;
const ll INF = 1e18;

int N, W;
int w[maxn], t[maxn];

bool ok(int mid) {
	ll f[maxw];
	f[0] = 0LL;
	for (int i = 1; i <= W; i++)	f[i] = -INF;

	for (int i = 1; i <= N; i++)
		for (int j = W; ~j; j--)
			if (f[j] > -INF) {
				int k = min(W, j + w[i]);
				f[k] = max(f[k], f[j] + t[i] - (ll)w[i] * mid);
			}
	return f[W] >= 0;
}

int main() {
	scanf("%d %d", &N, &W);
	for (int i = 1; i <= N; i++)
		scanf("%d %d", &w[i], &t[i]), t[i] *= 1000;

	int l = 0, r = 1e6, ans;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (ok(mid))	l = mid + 1, ans = mid;
		else	r = mid - 1;
	}
	return !printf("%d
", ans);
}