UVA 357 Let Me Count The Ways(全然背包)
The UVa count 背包 Let Me Ways 全然
2023-09-14 09:06:25 时间
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; }
相关文章
- Dissecting the Disruptor: Demystifying Memory Barriers
- The Animation in android
- service mysqld start 报错:service mysqld start 报错 090517 13:34:15 [ERROR] Can't open the mysql.plugin table. Please run mysql_upgrade to create it. 090Can't open the mysql.plugin table. Please run mysql
- UVA 11300 Spreading the Wealth (数学推导 中位数)
- [AngularFire2] Update multi collections at the same time with FirebaseRef
- [Cloud Architect] 11. Protecting Data Stored in the Cloud
- [AngularJS] Store the entry url and redirect to entry url after Logged in
- [ReactVR] Start a Virtual Reality Project Using the React VR CLI
- [Javascript] The JSON.stringify API
- [Javascript + rxjs] Introducing the Observable
- 错误消息sales area is not assigned for the header product
- 【习题 8-12 UVA - 1153】Keep the Customer Satisfied
- 【例题 6-17 UVa 10562】Undraw the Trees
- 【习题 5-10 UVA-1597】Searching the Web
- 【Uva 1601】The Morning after Halloween
- DL:深度学习算法(神经网络模型集合)概览之《THE NEURAL NETWORK ZOO》的中文解释和感悟(三)
- UVA - 10239 The Book-shelver's Problem
- 【大数据开发运维解决方案】记一次同事不慎用root起动weblogic以及启动日志卡在The server started in RUNNING mode 问题解决过程
- HDU - 1705 Count the grid