BOJ 15759 - Talent show (냅색, 이분탐색)

https://www.acmicpc.net/problem/15759

어려움

 

<문제설명>

최대 250마리의 소 n마리와 최대 1000의 무게제한W가 주어진다.

각각의 소는 최대 1e6의 무게w와 최대 1e3의 능력t가 주어진다.

 

소들을 적절히 골라서 무게합이 W이상인 집합 중, 능력합/무게합의 최대값을 x라고 할 때, 1000x의 소수점을 버린 값을 구하라.

 

<풀이>

고른 소들의 집합을 S라고하면 무게합은 W이상이고 다음을 만족해야 한다.

구해야 할 값은 1000x이므로 이를 y로 치환해서 다시 정리해 보면 다음과 같다.

 

y값 1~250*1000*1000범위에 대해 이분탐색하면 된다.

int pos(y) : 능력합/무게합이 y가 가능한지?

 

dp[k] : 무게 합이 k일 때 1000T - yW의 최대값

dp[W] : 무게합이 W이상일 떄 1000T - yW의 최대값

 

dp[W]>=0이면 가능하고, 그외엔 불가능하다.

 

<코드>

const int MAX = 1001;
const ll INF = 1e9;
ll n, W, dp[MAX];
P a[255];

bool pos(ll k) {
	fill(dp, dp + MAX, -INF);
	dp[0] = 0;
	for (ll i = 0, w, t; i < n; i++) {
		tie(w, t) = a[i];
		ll temp = 1000 * t - k * w;
		for (ll j = W; j >= 0; j--) {
			if (dp[j] == -INF) continue;
			dp[min(W, j + w)] = max(dp[min(W, j + w)], dp[j] + temp);
		}
	}
	return dp[W]>=0;
}

int main() {
	FAST; cin >> n >> W;
	for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;

	ll lo = 1, hi = 250*1000*1000+1;
	while (lo < hi) {
		int mid = (lo + hi+1) / 2;
		if (pos(mid)) lo = mid;
		else hi = mid - 1;
	}
	cout << lo << '\n';
}