博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
UVA 357 Let Me Count The Ways(全然背包)
阅读量:7238 次
发布时间:2019-06-29

本文共 614 字,大约阅读时间需要 2 分钟。

UVA 357 Let Me Count The Ways(全然背包)

题意:

       有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
#include
#include
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

转载地址:http://emrfm.baihongyu.com/

你可能感兴趣的文章
jquery ajax cache的问题
查看>>
VIM 与 系统剪切版
查看>>
我用iPad / iTouch来做什么
查看>>
php的mysql_insert_id()返回值问题
查看>>
css属性兼容
查看>>
Hadoop源码分析之心跳机制
查看>>
第三章初步了解函数
查看>>
[转] PHP常见的两个面试题
查看>>
asp.net MVC3 View视图
查看>>
利用Nginx搭建http和rtmp协议的流媒体服务器[转]
查看>>
面试笔试
查看>>
用CleanMyMac误删了语言包怎么办
查看>>
Java读写Word文件常用技术
查看>>
Android - View绘图原理总结
查看>>
按键精灵手机版监控像素变换点击脚本
查看>>
maven jar包上传到服务器
查看>>
SecureCrt退出全屏
查看>>
扩展功能==继承?
查看>>
HDU 4355 Party All the Time(三分|二分)
查看>>
算法笔记_223:打印回型嵌套(Java)
查看>>