有1分,2分,5分,10分四种硬币,每种硬币数量无限,给定n分钱,求有多少种组合可以组合成n分钱?

发布时间:2016-12-10 13:05:31 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"有1分,2分,5分,10分四种硬币,每种硬币数量无限,给定n分钱,求有多少种组合可以组合成n分钱?",主要涉及到有1分,2分,5分,10分四种硬币,每种硬币数量无限,给定n分钱,求有多少种组合可以组合成n分钱?方面的内容,对于有1分,2分,5分,10分四种硬币,每种硬币数量无限,给定n分钱,求有多少种组合可以组合成n分钱?感兴趣的同学可以参考一下。

一:利用母函数: using namespace std; int proc(int n){ vector<int> c1(n+1),c2(n+1); c1[0]=1;c1[1]=1;c1[2]=1;c1[5]=1;c1[10]=1; for(int k=2;k<=n;++k){ for(int i=0;i<=n;++i) for(int j=0;i+j<=n;j+=k){//这里j表示第k个表达式的指数,由于每次增幅为k,因为它要和前面的相乘了。 c2[i+j]+=c1[i]; } for(int i=0;i<=n;++i){ c1[i]=c2[i];c2[i]=0; } } return c1[n]; } int main(){ cout<< proc(4)<<endl; return 0; } 二:利用组合数的方法,其实好像可以说是背包问题的递归解。 int arr[]={1,2,5,10}; void dfs(int index,int n,vector<int>& vec){ if(n==accumulate(vec.begin(),vec.end(),0)){ for(size_t i=0;i<vec.size();++i) cout<<vec[i]<<" "; cout<<endl; } if(accumulate(vec.begin(),vec.end(),0)>n) return ; for(int i=index;i<4;++i){ vec.push_back(arr[i]); dfs(i,n,vec); vec.pop_back(); } } int main(){ vector<int> vec; dfs(0,4,vec); return 0; }

上一篇:《HTML5 从入门到精通--7.4 设置表格背景》
下一篇:漫谈:机器学习中距离和相似性度量方法

相关文章

相关评论