(动态规划)求有多少种不同的凑法

一个包可以装mg的东西，有n个物品，体积分别是a1,a2....an，要求选择的物品体积正好是m并且每个物品只能选择一次，一共有多少种不同的凑法？

思路：

如果m是0，则一个物品都不用选，return 1;

如果所有的物品都选上了，还不够m就return 0;

否则  如果不选第n个物品则选n-1个物品组成m加上选了第n个物品，那么就只需要选n0-1个组成m-a[n];

递归程序如下：

#include<iostream> using namespace std; int a[30]; int n; int f(int m,int n) { if(m==0)return 1; if(n<=0)return 0; else return f(m,n-1)+f(m-a[n],n-1); } int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; }cout<<f(40,n); return 0; } DP解法：

好像还有点问题，待解决........

#include<iostream> #include<cstring> using namespace std; int a[30],f[40][30]; int n; int main() { cin>>n; memset(f,0,sizeof(f)); for(int i=1;i<=n;++i) { cin>>a[i]; f[0][i]=1; } f[0][0]=1; for(int m=1;m<=40;++m) { for(int k=1;k<=n;++k) { f[m][k]=f[m][k-1]; if(m-a[k]>=0) f[m][k]+=f[m-a[k]][k-1]; } } cout<<f[40][n]; return 0; }