首页 > 代码库 > UVA 357 Let Me Count The Ways(完全背包)
UVA 357 Let Me Count The Ways(完全背包)
UVA 357 Let Me Count The Ways(完全背包)
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=293
题意:
有5种硬币: 1分 5分 10分 25分 和50分. 现在给你一个面值n, 问你有多少种方法能利用上述硬币组合出n分的金钱.
分析:
典型的完全背包问题.
本题的限制条件: 硬币钱数正好等于n
本题的目的条件: 求有多少种组合方法.
所以我们令dp[i][j]==x 表示用前i种硬币来构造j分金钱一共有x种方法.
初始化: dp为全0. 但dp[0][0]=1.
状态转移: dp[i][j] = sum( dp[i-1][j] , dp[i][j-val[i]])
前者表示第i种硬币一个都不选, 后者表示至少选1个第i种硬币来用.
最终所求: dp[5][n].
程序实现用的滚动数组, 逆序递推. 所以dp只有[j]这一维.
AC代码:
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn = 30000+5; int n=5; int val[]={1,5,10,25,50}; long long dp[maxn]; int main() { //初始化 memset(dp,0,sizeof(dp)); dp[0]=1; //递推 for(int i=0;i<n;i++) { for(int j=val[i];j<maxn;j++) dp[j] += dp[j-val[i]]; } //处理每个输入 int x; while(scanf("%d",&x)==1) { if(dp[x]==1) printf("There is only 1 way to produce %d cents change.\n", x); else printf("There are %lld ways to produce %d cents change.\n",dp[x],x); } return 0; }
UVA 357 Let Me Count The Ways(完全背包)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。