結果

問題 No.527 ナップサック容量問題
ユーザー hotpepsihotpepsi
提出日時 2017-06-13 00:03:35
言語 C++11
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 922 bytes
コンパイル時間 532 ms
コンパイル使用メモリ 60,888 KB
実行使用メモリ 13,756 KB
最終ジャッジ日時 2024-09-24 16:50:55
合計ジャッジ時間 4,001 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 TLE * 1 -- * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

int main(int argc, char *argv[])
{
	int n, v[100], w[100], sum = 0, mv;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> v[i] >> w[i];
		sum += w[i];
	}
	cin >> mv;
	int dp[100001];
	memset(dp, -1, sizeof(dp));
	int low = -1, high = 0;
	for (int t = 1; t <= sum; ++t) {
		memset(dp, -1, (t + 1) * sizeof(int));
		dp[0] = 0;
		int z = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = t; j >= w[i]; --j) {
				int k = dp[j - w[i]];
				if (k >= 0) {
					dp[j] = max(dp[j], k + v[i]);
				}
			}
		}
		int mm = 0;
		for (int i = 0; i <= t; ++i) {
			mm = max(mm, dp[i]);
		}
		if (mm == mv) {
			if (low < 0) {
				low = t;
			}
			high = t;
		} else if (mm > mv) {
			break;
		}
	}
	cout << low << endl;
	if (high == sum) {
		cout << "inf" << endl;
	} else {
		cout << high << endl;
	}
	return 0;
}
0