aoj2331～2340 - c21coterie @ ウィキ

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