https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=615
题意是有五种面值不同的硬币，每种都可以用无限个，问组合成给定价值有多少种组合方法
1.母函数求解，
#include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<string> #include<algorithm> #include<queue> #include<vector> #include<map> #include<set> #define eps 1e-9 #define PI 3.141592653589793 #define bs 1000000007 #define bsize 256 #define MEM(a) memset(a,0,sizeof(a)) #define inf 0x3f3f3f3f #define rep(i,be,n) for(i=be;i<n;i++) typedef long long ll; using namespace std; int a[10000],b[10000]; int main() { int i,j,k,n,s[5]={1,5,10,25,50}; a[0]=1; for(i=0;i<5;i++) { for(j=0;j<=7500;j++) { for(k=1;k*s[i]+j<=7500;k++) b[k*s[i]+j]+=a[j]; } for(j=s[i];j<=7500;j++) { a[j]=b[j];//保存上一层的系数 } } while(~scanf("%d",&n)) printf("%d\n",a[n]); return 0; }
2.完全背包,递推状态，写法更简单
#include<stdio.h> #include<string.h> int dp[20000],n,i,j; int main() { memset(dp,0,sizeof(dp)); dp[0]=1; int s[5]={1,5,10,25,50}; for(i=0;i<5;i++) { for(j=s[i];j<7500;j++) { dp[j]+=dp[j-s[i]]; } } while(~scanf("%d",&n)) { printf("%d\n",dp[n]); } return 0; }
