| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 6950 人关注过本帖, 1 人收藏
标题:动态规划 ——找零钱
只看楼主 加入收藏
编译中。。
Rank: 7Rank: 7Rank: 7
来 自:中国
等 级:黑侠
帖 子:198
专家分:511
注 册:2011-7-29
结帖率:75%
收藏(1)
已结贴  问题点数:100 回复次数:11 
动态规划 ——找零钱
描述
我们知道人民币有1、2、5、10、20、50、100这几种面值。
现在给你n(1≤n≤250)元,让你计算换成用上面这些面额表示且总数不超过100张,共有几种。
比如4元,能用4张1元、2张1元和1张2元、2张2元,三种表示方法。
输入
输入有多组,每组一行,为一个整合n。
输入以0结束。
输出
输出该面额有几种表示方法。
样例输入
1
4
0
样例输出
1
3


想半天不知道用DP怎么写,求代码一定要带上注释啊。。。
              最近学的有的郁闷,卡了一天,希望能有人指点一下。
搜索更多相关主题的帖子: 人民币 动态 
2014-12-01 12:52
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
收藏
得分:34 
动态规划不会,穷举法的有一个
#include<stdio.h>
#include<malloc.h>
#include<math.h>

int A[7] = {1, 2, 5, 10, 20, 50, 100};
int count = 0;

void dfs(int n, int top, int s);

int main()
{
    int n;
   
    scanf("%d", &n);
    while (n != 0)
    {
        count = 0;
        dfs(n, 6, 0);
        printf("%d\n", count);
        scanf("%d", &n);
    }
   
    return 0;
}

void dfs(int n, int top, int s)
{
    int i;
   
    if (n == 0)
    {
        count++;
        return ;
    }
    if (top < 0)
        return ;
   
    dfs(n, top-1, s); //先不用A[top]这种货币看看
    for (i=A[top]; i<=n; i+=A[top])
    {
        if (s == 100)//总数不超过100张
            return ;
        dfs(n-i, top-1, ++s);
    }
}

[ 本帖最后由 巧若拙 于 2014-12-3 07:44 编辑 ]
2014-12-01 14:56
编译中。。
Rank: 7Rank: 7Rank: 7
来 自:中国
等 级:黑侠
帖 子:198
专家分:511
注 册:2011-7-29
收藏
得分:0 
。。继续求大神

 当我感到些许疲倦时   便想躺在阳光下,小路旁 . 可这些往往都是奢望..
2014-12-01 23:08
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:34 
发代码上来先看着。如果实在看不懂,改天有时间我再做解释。

程序代码:
#include <stdio.h>

int cal(int n)
{
    const int a[] = {1, 2, 5, 10, 20, 50, 100};
    int f[101][256] = {1};
    int i, j, k;

    for(i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    for(j = 1; j <= 100; j++)
    for(k = a[i]; k <= n; k++)
        f[j][k] += f[j - 1][k - a[i]];

    for(k = 0, i = 1; i <= 100; k += f[i++][n]);
    return k;
}

int main()
{
    int n;
    for(; scanf("%d", &n) != EOF; printf("%d\n", cal(n)));
    return 0;
}

重剑无锋,大巧不工
2014-12-02 16:07
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
收藏
得分:0 
虽然还不是很理解动态规划,但依然斗胆献丑,把自己对楼上代码的理解贴出来,并增加一点点自己的看法。顺便问一句,这个算法的思路是不是和Floyd 算法有点相似?
程序代码:
int cal(int n)
{
    const int a[] = {1, 2, 5, 10, 20, 50, 100};
    int f[101][256] = {1};//f[m][n]的含义为用m张钞票构成的金额为n的组合数量 
    int i, j, k, min, max;

    for(i = 0; i < sizeof(a) / sizeof(a[0]); i++)//钞票面值 
    {
        for(j = 1; j <= 100; j++)//钞票张数 
        {
            min = (j > a[i]) ? j : a[i]; //为避免无效运算,给k值规定一个上限和下限 
            max = (n <= j * a[i]) ? n : j * a[i];
            for(k = min; k <= max; k++)//金额总数 
            {
                f[j][k] += f[j - 1][k - a[i]];//该组合中含有一张面值为a[i]的钞票
            }
        }    
    }
    
    for(k = 0, i = 1; i <= 100; k += f[i++][n]);
    
    return k;
}
2014-12-03 17:52
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
收藏
得分:0 
为了理解这个问题,特意去看了看有关动态规划算法相关文章,里面一句话印象深刻:动态规划算法的有效性依赖于问题本身所具有的两个重要性质:最优子结构性质和子问题重叠性质。
1、最优子结构:当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。
2、重叠子问题:在用递归算法自顶向下解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只解一次,而后将其解保存在一个表格中,在以后尽可能多地利用这些子问题的解。

找钱问题的子问题从小到大依次是利用面值为a[i]的钞票,计算金额为k时需要j张钞票的组合数量,这里的a[i],k和j都是从小到大,因为规模较大时可以利用小规模问题计算的结果,反之则不行。a[i],k和j构成三层循环,a[i]一定要在最外层,k和j的顺序可互换。算法思路有些类似Floyd 算法。
根据上述理解,我写了一个和beyondyf提供的算法相似的代码,只不过k和j的位置换了一下。
初次接触动态规划,理解可能有些不当,请大牛们指正。

程序代码:
int cal_2(int n)
{
    const int a[] = {1, 2, 5, 10, 20, 50, 100};
    int f[256][101] = {1};//f[n][m]的含义为用m张钞票构成的金额为n的组合数量 
    int i, j, k, max;

    for(i = 0; i < sizeof(a) / sizeof(a[0]); i++)//钞票面值 
    {
        for(k = a[i]; k <= n; k++)//金额总数 
        {
            max = (k < 100) ? k : 100;
            for(j = 1; j <= max; j++)//钞票张数 
                f[k][j] += f[k-a[i]][j-1];//该组合中含有一张面值为a[i]的钞票
        }
    }
        
    k = 0;
    for(i=1; i<=100; i++)
        k += f[n][i];

    return k;
}
2014-12-04 07:12
tlliqi
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:204
帖 子:15453
专家分:65956
注 册:2006-4-27
收藏
得分:34 
学习
2014-12-04 08:23
编译中。。
Rank: 7Rank: 7Rank: 7
来 自:中国
等 级:黑侠
帖 子:198
专家分:511
注 册:2011-7-29
收藏
得分:0 
最近比较忙,3天没来论坛,看到大家回复,先结帖 在好好理解一下

 当我感到些许疲倦时   便想躺在阳光下,小路旁 . 可这些往往都是奢望..
2014-12-04 14:03
编译中。。
Rank: 7Rank: 7Rank: 7
来 自:中国
等 级:黑侠
帖 子:198
专家分:511
注 册:2011-7-29
收藏
得分:0 
回复 6 楼 巧若拙
你的注释很棒,否则根本看不懂版主大人的回复。我再加一个我自己的理解吧。

程序代码:
f[k][j] += f[k-a[i]][j-1];  //这里是最关键的,也是动态规划的核心,
下面是我调试理解这个程序的时候,打印出来的结果。我分析之后才明白,
比如 f[2][1]+=f[1][0]]=0   表示当子问题为金额2元时,用1张纸币如何获得最优解
因为之前已经包含了一张a[i]元的纸币,这里a[i]=1,所以这个子问题的最优解就是,去掉
a[i]元钱(1元钱)和去掉a[i]元钱的容量(即一张)的最优解。。 
从小规模循环至答案。




4
f[1][1]+=f[1-a[0]][1-1]]=1
f[1][1]+=f[0][0]]=1
f[2][1]+=f[2-a[0]][1-1]]=0
f[2][1]+=f[1][0]]=0
f[2][2]+=f[2-a[0]][2-1]]=1
f[2][2]+=f[1][1]]=1
f[3][1]+=f[3-a[0]][1-1]]=0
f[3][1]+=f[2][0]]=0
f[3][2]+=f[3-a[0]][2-1]]=0
f[3][2]+=f[2][1]]=0
f[3][3]+=f[3-a[0]][3-1]]=1
f[3][3]+=f[2][2]]=1
f[4][1]+=f[4-a[0]][1-1]]=0
f[4][1]+=f[3][0]]=0
f[4][2]+=f[4-a[0]][2-1]]=0
f[4][2]+=f[3][1]]=0
f[4][3]+=f[4-a[0]][3-1]]=0
f[4][3]+=f[3][2]]=0
f[4][4]+=f[4-a[0]][4-1]]=1
f[4][4]+=f[3][3]]=1
f[2][1]+=f[2-a[1]][1-1]]=1
f[2][1]+=f[0][0]]=1
f[2][2]+=f[2-a[1]][2-1]]=1
f[2][2]+=f[0][1]]=1
f[3][1]+=f[3-a[1]][1-1]]=0
f[3][1]+=f[1][0]]=0
f[3][2]+=f[3-a[1]][2-1]]=1
f[3][2]+=f[1][1]]=1
f[3][3]+=f[3-a[1]][3-1]]=1
f[3][3]+=f[1][2]]=1
f[4][1]+=f[4-a[1]][1-1]]=0
f[4][1]+=f[2][0]]=0
f[4][2]+=f[4-a[1]][2-1]]=1
f[4][2]+=f[2][1]]=1
f[4][3]+=f[4-a[1]][3-1]]=1
f[4][3]+=f[2][2]]=1
f[4][4]+=f[4-a[1]][4-1]]=1
f[4][4]+=f[2][3]]=1
3

 当我感到些许疲倦时   便想躺在阳光下,小路旁 . 可这些往往都是奢望..
2014-12-04 14:50
编译中。。
Rank: 7Rank: 7Rank: 7
来 自:中国
等 级:黑侠
帖 子:198
专家分:511
注 册:2011-7-29
收藏
得分:0 
动态规划很难,对于我来说给出转移方程说不定也写不了。,,

 当我感到些许疲倦时   便想躺在阳光下,小路旁 . 可这些往往都是奢望..
2014-12-04 14:51
快速回复:动态规划 ——找零钱
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.023010 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved