tyvj p 1096 0-1リュックサック種数を求める
N個の数の中でその和がMのいくつかの数を探し出す.正の整数N(1
入力形式Input Format
1行目はNとMを表す2つの数字です.2行目からN個の数です.
出力フォーマットOutput Format
1つの数字について、Mの組み合わせの個数を表します.
サンプル入力Sample Input[データのコピー]
4 4 1 1 2 2
サンプル出力Sample Output[コピーデータ]
3
時間制限時間
各試験点1 s
//d[j]=d[j]+d[j-a[i]], j=0 ， ， d[0]=1;
#include <iostream>
#include <cstring>
using namespace std;
int a[105],d[10005];
int main()
{
int n,m,i,j;
while(cin>>n>>m)
{
for(i=1;i<=n;i++) cin>>a[i];
memset(d,0,sizeof(d));
d[0]=1;
for(i=1;i<=n;i++)
for(j=m;j>=a[i];j--)
d[j]=d[j]+d[j-a[i]];
cout<<d[m]<<endl;
}
return 0;
}