频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
uva 674 - Coin Change
2012-08-13 11:39:35      个评论      
收藏   我要投稿

题目意思: 有5种硬币 1 , 5 , 10  , 25  , 50 ,现在给我们一个数n,求用这5种硬币组成和为n的总方案数是多少

解题思路:   动态规划
                     1:如果硬币只由1分组成,那么总方案数就是1
                     2:如果硬币由1和5组成,那么总方案数就是1+s1 (s1为1和5组成的方案)
                     .
                     .
                     .
                    6:如果硬币由1,5,10,25,50组成,那么总方案数就是1+s1+s2+s3+s4+s5
                    题目给出的数据n最大为7489,那么我们采用的是先把所有的值的拆分的总方案数求出来(也就是打表),然后输入一个我么直接输出即可。
                    思路:我们用type[5]数组存储5种硬币,设dp[i][j]表示用前i+1种(type[0]....type[i])组成价值为j的总方案数,那么我么就可以直接两重循环去枚举每一个价值j,求出所有的数据,最后查找输出。

代码:
[cpp] 
//(没有优化) 
#include <algorithm> 
#include <iostream> 
#include <cstring> 
#include <string> 
#include <vector> 
#include <cstdio> 
#include <stack> 
#include <queue> 
#include <cmath> 
using namespace std; 
#define MAXN 8000 
 
int type[5] = {1,5,10,25,50}; 
int dp[5][MAXN];//用int类型即可,如果MAXN上万要用unsigned long long 
int n , ans; 
 
//打表处理好所有的数据 
void solve(){ 
    for(int i  = 0 ; i < 5 ; i++){ 
        for(int j = 0 ; j < MAXN ; j++){ 
            if(i == 0 || j == 0) dp[i][j] = 1;//i为0说明只由1组成那么dp[i][j]为1,j为0说明价值为0的组成方案只有1种(如果看成0则会WA) 
            else dp[i][j] = 0;//其它全部初始化为0 
        } 
    }     
    for(int i = 1 ; i < 5 ; i++){//i-1出现,那么从1开始枚举 
        for(int j = 1 ; j < MAXN ; j++){ 
            for(int k = 0 ; k*type[i] <= j ; k++)//k个type[i],注意必须从0开始 
                dp[i][j] += dp[i-1][j-k*type[i]];//加上前面的方案数 
       } 
    } 

 
int main(){ 
    //freopen("input.txt" , "r" , stdin); 
    solve(); 
    while(scanf("%d" , &n) != EOF){ 
        for(int i = 4 ; i >= 0 ; i--){ 
            if(dp[i][n]) { ans =  dp[i][n] ; break;}//从末尾开始查找只要有一个不为0就是答案 
        } 
        printf("%d\n" , ans); 
    } 
    return 0; 

 
 
 
 
//(将二维优化成一维)优化后的代码 
#include <algorithm> 
#include <iostream> 
#include <cstring> 
#include <string> 
#include <vector> 
#include <cstdio> 
#include <stack> 
#include <queue> 
#include <cmath> 
using namespace std; 
#define MAXN 8000 
 
int type[5] = {1,5,10,25,50}; 
int dp[MAXN];//dp[i]表示价值i的总的方案数 
int n , ans; 
 
//打表处理好所有的数据 
void solve(){ 
    memset(dp , 0 , sizeof(dp)) ; dp[0] = 1;//注意dp[0] = 1这个条件 
    for(int i = 0 ; i < 5 ; i++){ 
        for(int j = 1 ; j < MAXN ; j++){ 
          if(j-type[i] >= 0) dp[j] += dp[j-type[i]];//累加起来 
       } 
    } 

 www.2cto.com
int main(){ 
    //freopen("input.txt" , "r" , stdin); 
    solve(); 
    while(scanf("%d" , &n) != EOF) printf("%d\n" , dp[n]); 
    return 0; 


作者:cgl1079743846
点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:SWIG入门3: C/C++初级特性
下一篇:uva 357 - Let Me Count The Ways 和 uva 147 - Dollars
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站