※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「aoj2231~2240」の編集履歴(バックアップ)一覧に戻る

aoj2231~2240 - (2013/01/28 (月) 10:09:40) の1つ前との変更点

追加された行は青色になります

削除された行は赤色になります。

+*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";
+ 	}
+ }