結果

問題 No.527 ナップサック容量問題
コンテスト
ユーザー agis
提出日時 2017-06-10 00:18:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,553 bytes
コンパイル時間 1,602 ms
コンパイル使用メモリ 170,964 KB
実行使用メモリ 13,884 KB
最終ジャッジ日時 2024-09-22 20:59:55
合計ジャッジ時間 5,189 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 RE * 1 TLE * 1
other -- * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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;
	rep(i, N) {
		cin >> v[i] >> w[i];
		maxw += w[i];
	}
	cin >> V;
	bool flag = false;
	vector<int>ans;
	int k;
	int x;
	if (DP(0, maxw) == V) {
		flag = true;
	}
	int left = 1;
	int right = maxw;
	while (1) {		//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 (1) {
		memset(dp, -1, sizeof(dp));
		x = DP(0, k);
		if (x >= V)k--;
		if (x < V) {
			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 (1) {
		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 << ans[0] << endl << "inf" << endl;
	}
	else {
		cout << ans[0] << endl << ans[ans.size() - 1] << endl;
	}
	return 0;
}
0