题目描述
给定N个正整数A1,A2,…,AN,从中选出若干个数,使它们的和为M,求有多少种选择方案。
输入格式
第一行包含两个整数N和M。
第二行包含N个整数,表示A1,A2,…,AN。
输出格式
包含一个整数,表示可选方案数。
数据范围
1≤N≤100,
1≤M≤10000,
1≤Ai≤1000
输入样例:
样例
输入样例:
4 4
1 1 2 2
输出样例:
3
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=10010;
int n,m;
int f[N];
int main(){
cin>>n>>m;
f[0]=1;//边界:体积为0时,一种方案:都不选
while(n--){
int v;
cin>>v;
for(int i=m;i>=v;i--)f[i]+=f[i-v];
}
cout<<f[m];
return 0;
}