「aoj2231~2240」の編集履歴(バックアップ)一覧に戻る
aoj2231~2240」を以下のとおり復元します。
*2333 My friends are small
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2333
ナップザック問題のうち最大限入れられる組み合わせの数だけ計算する問題。

解法
組み合わせの集合を排他的に分けます。
おもちゃの重さを小さい順に並べ、後は入れないことに決めた一番最後に入れる一番小さなおもちゃを決めてそれを入れない場合をナップザック問題の手法で計算します。
入れないことに決めたおもちゃを最後に入れようとしてはいらない組み合わせだけ集計すれば答えが出ます。



 #include<stdio.h>
 #include<vector>
 #include<string.h>
 #include<iostream>
 #include<algorithm>
 int main(){
 	long long int ans=0,mod=1000000007;
 	int n,w,g,sum=0;
 	std::vector<int> ws;
 	scanf("%d %d",&n,&w);
 	for(int i=0;i<n;i++){
 		scanf("%d",&g);
 		ws.push_back(g);
 	}
 	
 	std::sort(ws.begin(),ws.end());
 	int m=ws[0];
 	for(int i=0;i<ws.size();i++){
 		long long int memo[10002]={0};
 		if(sum>w)break;
 		memo[sum]=1;
 		for(int j=i+1;j<ws.size();j++){
 			int g=ws[j];
 			for(int k=w-g;k>=0;k--){
 				memo[k+g]=(memo[k+g]+memo[k])%mod;
 			}
 		}
 		for(int k=w;k>=0&&k>w-ws[i];k--){
 			ans=(ans+memo[k])%mod;
 		}
 		sum+=ws[i];
 	}
 	if(sum<=w||m>w){
 		printf("1\n");
 	}else{
 		std::cout<<ans<<"\n";
 	}
 }

復元してよろしいですか?