题目描述
给定N个正整数$A_1,A_2,…,A_N$,从中选出若干个数,使它们的和为M,求有多少种选择方案。
算法:01背包
时间复杂度:O($N*M$)
需要注意
状态表示为体积恰好为j的选择方案的数量,需要给出在f[0]的初始值
C++代码
#include<iostream>
using namespace std;
const int M=10010;
int f[M];
int n,m;
int main()
{
cin>>n>>m;
f[0]=1;
for(int i=1;i<=n;i++){
int t;
scanf("%d",&t);
for(int j=m;j>=t;j--)
f[j]+=f[j-t];
}
cout<<f[m]<<endl;
return 0;
}