結果

問題 No.527 ナップサック容量問題
ユーザー watamario15watamario15
提出日時 2017-11-22 18:01:22
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 788 bytes
コンパイル時間 363 ms
コンパイル使用メモリ 55,384 KB
実行使用メモリ 42,496 KB
最終ジャッジ日時 2024-05-04 21:01:38
合計ジャッジ時間 8,400 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 14 ms
42,368 KB
testcase_01 AC 27 ms
42,496 KB
testcase_02 RE -
testcase_03 RE -
testcase_04 AC 15 ms
42,368 KB
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 AC 21 ms
42,496 KB
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 AC 28 ms
42,368 KB
testcase_31 AC 27 ms
42,368 KB
testcase_32 RE -
testcase_33 RE -
testcase_34 AC 28 ms
42,496 KB
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
using namespace std;

int sht[100][100001];

int main(void){
 int N,V,v[100],w[100],i,j,W_max=0,temp,cnt=0,min=-1,max=-1;
 cin>>N;
 for(i=0;i<N;i++){
 	cin>>v[i]>>w[i];
	W_max=W_max+w[i];
 }
 cin>>V;
 
 for(i=0;i<100;i++){
 	for(j=0;j<100001;j++){
		sht[i][j]=0;
	}
 }
 
 sht[w[0]][0]=v[0];
  
 for(i=0;i<=W_max;i++){
 	for(j=1;j<N;j++){
		if(i-w[j]>=0){
			temp=sht[i-w[j]][j-1]+v[j];
			if(sht[i][j-1]<=temp){
				sht[i][j]=temp;
			}else{
				sht[i][j]=sht[i][j-1];
			}
		}else{
 			sht[i][j]=sht[i][j-1];
		}
	}
	if(sht[i][N-1]==V){
		cnt++;
		if(cnt==1) min=i;
	}
	if(sht[i][N-1]>V){
		max=i-1;
		break;
	}
 }
 
 if(min==0) min=1;
 if(min==-1) min=W_max;
 
 cout<<min<<endl;
 if(max==-1 || max<min){
 	cout<<"inf"<<endl;
 }else{
 	cout<<max<<endl;
 }
 return 0;
}
0