結果

問題 No.527 ナップサック容量問題
ユーザー MNghr
提出日時 2017-06-09 23:48:43
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 873 bytes
コンパイル時間 567 ms
コンパイル使用メモリ 60,816 KB
実行使用メモリ 13,760 KB
最終ジャッジ日時 2024-09-22 20:10:14
合計ジャッジ時間 4,099 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 TLE * 1 -- * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
using namespace std;
int N,v[100],w[100],V;

int rec(int i,int j){
	int res;
	if(i == N)
		res = 0;
	else if(j < w[i])
		res = rec(i+1,j);
	else
		res = max(rec(i+1,j),rec(i+1,j-w[i]) + v[i]);

	return res;
}

int main(){
	bool flag1= true,flag2=false,flag3=false,flag4 = true;
	int sum = 0;
	cin >> N;
	for(int i = 0;i < N;++i)
		cin >> v[i] >> w[i];
	cin >> V;

	for(int i = 0 ;i < N;++i){
		sum += v[i];
	}

	for(int i = 1; i < 100000;++i){
		if(rec(0,i) == V && flag1 == true){
			cout << i <<endl;
			flag1 = false;
			flag2 = true;
		}

		if(sum <= V && flag4 == true && flag2 == true){
			cout << "inf" <<endl;
			flag3 == true;
			flag4 = false;
		}
		else if(flag2 == true && rec(0,i+1) != V){
			cout << i << endl;
			break;
		}

		if(flag3 == true && flag2 == true)
			break;

	}



}
0