好贷网好贷款

hdu 2844 Coins

发布时间:2016-12-4 3:50:39 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 2844 Coins",主要涉及到hdu 2844 Coins方面的内容,对于hdu 2844 Coins感兴趣的同学可以参考一下。

hdu   2844   Coins               题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2844 题目大意:有n种硬币,给出价值上限m,给出这n中硬币的价值和数量,求价值上限内的价值组合数。 题目分析:看起来像是个不设重量的多重背包,求组合数可以与母函数结合。 code: #include<stdio.h> #include<string.h> int main() { int i,j,ans,dp[100010],a[110],c[110],count[100010],m,n; while(scanf("%d%d",&n,&m),n||m) { for(i=0;i<n;i++) scanf("%d",&a[i]); for(i=0;i<n;i++) scanf("%d",&c[i]); memset(dp,0,sizeof(dp)); for(i=0;i<n;i++) { memset(count,0,sizeof(count)); for(j=a[i];j<=m;j++) { if(dp[j-a[i]]+a[i]>dp[j]&&count[j-a[i]]+1<=c[i]) { dp[j]=dp[j-a[i]]+a[i]; count[j]=count[j-a[i]]+1; } } } for(ans=0,i=1;i<=m;i++) { ans+=dp[i]==i?1:0; } printf("%d\n",ans); } return 0; }PS:用dp[i]表示当前容量是i时的最大价值,那么,我们求的就是可以组合出1-m这些价值的哪些价值,我们只需要统计最后dp[i]==i的个数,即可,dp[i]==i就表示容量是i,价值也是i,只要这个i是1-m间的,那么就是答案的其中一个。——代码分析

上一篇:sdram工作原理
下一篇:nyoj 20

相关文章

关键词: hdu 2844 Coins

相关评论