結果

問題 No.527 ナップサック容量問題
ユーザー agis
提出日時 2017-06-10 00:38:57
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,612 bytes
コンパイル時間 1,560 ms
コンパイル使用メモリ 170,900 KB
実行使用メモリ 13,880 KB
最終ジャッジ日時 2024-09-22 21:16:53
合計ジャッジ時間 5,181 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 TLE * 1 -- * 34
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:43:13: warning: 'k' may be used uninitialized [-Wmaybe-uninitialized]
   43 |         int k;
      |             ^

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

int dp[100 + 1][1000 + 1];
int N;
int v[100], w[100];
int DP(int i, int j) {
	if (dp[i][j] != -1) {
		return dp[i][j];
	}
	int res;
	if (i == N) {
		res = 0;
	}
	else if (j < w[i]) {
		res = DP(i + 1, j);
	}
	else {
		res = max(DP(i + 1, j), DP(i + 1, j - w[i]) + v[i]);
	}
	return dp[i][j] = res;
}

int main() {
	cin.sync_with_stdio(false);
	int V;
	cin >> N;
	int maxw=0,maxv=0;
	rep(i, N) {
		cin >> v[i] >> w[i];
		maxw += w[i];
		maxv += v[i];
	}
	cin >> V;
	memset(dp, -1, sizeof(dp));
	bool flag = false;
	vector<int>ans;
	int k;
	int x;
	if (DP(0, maxw) == V) {
		flag = true;
	}
	int left = 1;
	int right = maxw;
	while (flag==0) {		//min
		memset(dp, -1, sizeof(dp));
		k = (left + right) / 2;
		x = DP(0, k);
		if (x >= V) {
			right = k;
		}
		else {
			left=k;
		}
		if (x == V) break;
	}
	while (flag==0) {
		memset(dp, -1, sizeof(dp));
		x = DP(0, k);
		if (x >= V)k--;
		if (x < V||k==0) {
			ans.push_back(k + 1);
			break;
		}
	}
	left = 1;
	right = maxw;
	while (flag==0) {	//max
		memset(dp, -1, sizeof(dp));
		k = (left + right) / 2;
		x = DP(0, k);
		if (x > V) {
			right = k;
		}
		else {
			left = k;
		}
		if (x == V)break;
	}
	while (flag==0) {
		memset(dp, -1, sizeof(dp));
		x = DP(0, k);
		if (x <= V)k++;
		if (x > V) {
			ans.push_back(k - 1);
			break;
		}
	}

	if (flag) {
		cout << maxw << endl << "inf" << endl;
	}
	else {
		cout << ans[0] << endl << ans[1] << endl;
	}
	return 0;
}
0