結果

問題 No.527 ナップサック容量問題
ユーザー aaa
提出日時 2018-11-11 13:00:48
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,217 bytes
コンパイル時間 1,076 ms
コンパイル使用メモリ 104,420 KB
実行使用メモリ 33,664 KB
最終ジャッジ日時 2024-11-29 15:14:23
合計ジャッジ時間 7,537 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 WA * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>

using namespace std;


int main() {
	int i, j;
	int n, V;
	vector<int>v, w;
	vector<int>dp(100005, 0);
	vector<vector<int>>flag(100005);

	cin >> n;

	for (i = 0; i < n; i++) {
		int num1, num2;
		cin >> num1 >> num2;
		v.push_back(num1);
		w.push_back(num2);
		dp[num2] = num1;
		flag[num2].push_back(i);
	}

	cin >> V;

	//dp[0] = 1;

	for (int W = 1; W <= 100000; W++) {

		bool flag2 = false;
		for (i = 0; i < n; i++) {
			if (W >= w[i]) {

				if (W - w[i] != 0 && dp[W - w[i]] == 0) {
					continue;
				}
				int num = 0;
				/*	if (dp[W - w[i]] == 0) {
						num = 0;
					}
					else {*/
				auto itr = std::find(flag[W - w[i]].begin(), flag[W - w[i]].end(), i);
				if (itr != flag[W - w[i]].end()) {
					//dp[W] = dp[W - 1];
					//flag[W] = flag[W - 1];
					continue;
				}
				else {
					num = dp[W - w[i]] + v[i];
					//if (W - w[i] != 0) {
						//flag[W - w[i]].push_back(i);
					flag[W].push_back(i);
					//}
					//flag[W - w[i]].push_back(i);
					//flag[W] = flag[W - w[i]];
					//flag[W].push_back(i);
					//flag[W].push_back(flag[W - w[i]]);
				}
				//}
				if (num > dp[W - 1]) {
					dp[W] = num;
					flag2 = true;
				}
				else if (num < dp[W - 1]) {
					//dp[W] = dp[W - 1];
					//flag[W] = flag[W - 1];
				}

				//dp[W] = max({ dp[W], num, dp[W - 1] });

			}
		}

		if (flag2 == false) {
			dp[W] = dp[W - 1];
			flag[W] = flag[W - 1];
		}

	}

	vector<int>list;

	for (i = 0; i <= 1000; i++) {
		if (dp[i] == V) {
			list.push_back(i);
		}
	}

	sort(list.begin(), list.end());

	if (list.size() >= 1 && list[0] == 0){
		list.erase(list.begin());
	}

	if (list.size() == 0) {

	}
	else {
		
		int minn = list[0];
		cout << minn << endl;

		//if (list[list.size() - 1] == dp[minn]) {
		if (dp[999] == dp[minn]) {
			cout << "inf" << endl;
		}
		else {
			cout << list[list.size() - 1] << endl;
		}

	}
	


	getchar();
	getchar();
	return 0;
}
0