結果

問題 No.527 ナップサック容量問題
ユーザー watamario15
提出日時 2017-11-22 18:01:22
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
RE  
実行時間 -
コード長 788 bytes
コンパイル時間 364 ms
コンパイル使用メモリ 55,136 KB
実行使用メモリ 42,496 KB
最終ジャッジ日時 2024-11-26 11:18:31
合計ジャッジ時間 9,898 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 RE * 1
other AC * 5 RE * 32
権限があれば一括ダウンロードができます

ソースコード

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