hdu1284 sdut2777 钱币兑换问题（完全背包,递推,母函数）

本文主要是介绍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+x²+x³+…)*( 1+x²+x⁴+x⁶+…)*( 1+x³+x⁶+x⁹+…)

将其展开取相应指数项的系数即可（指数代表钱的面值，系数代表方案数）

#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 钱币兑换问题（完全背包,递推,母函数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！