本文主要是介绍hdu1284 sdut2777 钱币兑换问题（完全背包,递推,母函数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
钱币兑换问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4735 Accepted Submission(s): 2675
Problem Description
在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。
Input
每行只有一个正整数N，N小于32768。
Output
对应每个输入，输出兑换方法数。
Sample Input
2934 12553
Sample Output
718831 13137761
分析：
就是政治老师讲的怎么忘瓶子里装石沙水的问题，要想装得满，先装石头再装沙子最后灌水！
所以只肖考虑换多少3分钱，再考虑用2毛钱有多少种替换方法，1分的自动填满
#include<stdio.h>
int main()
{int i,n,s;while(scanf("%d",&n)!=EOF){s=n/3+1;for(i=0;i<=n/3;i++)s+=(n-i*3)/2;printf("%d\n",s);}return 0;
}
完全背包做法：
#include<stdio.h>
int dp[32768];
int main()
{int i,j,n;dp[0]=1;for(i=1; i<=3; i++)for(j=i; j<32768; j++)dp[j]+=dp[j-i];while(scanf("%d",&n)!=EOF){printf("%d\n",dp[n]);}return 0;
}
递推：
http://hi.baidu.com/shenghao_200/item/6df741079aba53db1ef0465c
http://wenwen.soso.com/z/q181589609.htm
#include<stdio.h>
int a[32768];
int main()
{int n,i;a[0]=0;for(i = 1 ; i < 32768 ; i++){if(i%6==1&&i!=1)a[i]=a[i-1]+(i/6);else a[i]=a[i-1]+(i/6+1);}while(scanf("%d",&n)!=EOF)printf("%d\n",a[n]);return 0;
}母函数：
定义母函数
G(x)=(1+x+x2+x3+…)*( 1+x2+x4+x6+…)*( 1+x3+x6+x9+…)
将其展开取相应指数项的系数即可（指数代表钱的面值，系数代表方案数）
#include<stdio.h>
#define max 32768
int ans[max],ans2[max],ans3[max];
int main()
{int i,j,n;for(i=0; i<max; i++)ans[i]=1;for(i=0; i<max; i++)for(j=0; i+j<max; j+=2)ans2[i+j]+=ans[i];for(i=0; i<max; i++)for(j=0; i+j<max; j+=3)ans3[i+j]+=ans2[i];while(scanf("%d",&n)!=EOF)printf("%d\n",ans3[n]);return 0;
}这篇关于hdu1284 sdut2777 钱币兑换问题（完全背包,递推,母函数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
