//
给定N个正整数A1,A2,…,AN,从中选出若干个数,使它们的和为M,求有多少种选择方案。
//
状态表示为:从前i个数中开始选,并且和恰好为j的方案个数
状态转移方程:
总的方案分为选第i个+不选第i个数。
不选第i个数,也就是从前i-1个数中开始选,并且和为j的方案数量。f[i][j]=f[i-1][j];
选第i个数:就是看全部物品,又因为每个方案的第i个数相等,所以就可以看前i-1个数,并且总和为m-v的方案数量。为f[i][j]=f[i-1][j-v];
同样的因为当体积为0时,方案数只有f[0][0]=1,其余的可赋为0;
f[0]=1;
for(int i=0;i<n;i++)
{
int v;
cin>>v;
for(int j=m;j>=v;j--)
f[j]+=f[j-v];
}