首页 > 专题系列 > 算法分析 > 动态规划(7)-硬币找零
2014
03-10

动态规划(7)-硬币找零

问题:

假设有m种面值不同的硬币,个个面值存于数组S ={S1,S2,… Sm}中,现在用这些硬币来找钱,各种硬币的使用个数不限。 求对于给定的钱数N,我们最多有几种不同的找钱方式。硬币的顺序并不重要。

例如,对于N = 4,S = {1,2,3},有四种方案:{1,1,1,1},{1,1,2},{2,2},{1, 3}。所以输出应该是4。对于N = 10,S = {2,5, 3,6},有五种解决办法:{2,2,2,2,2},{2,2,3,3},{2,2,6 },{2,3,5}和{5,5}。所以输出应该是5。

1)最优子结构
要算总数的解决方案,我们可以把所有的一整套解决方案在两组 (其实这个方法在组合数学中经常用到,要么包含某个元素要么不包含,用于递推公式等等,)。
1)解决方案不包含 第m种硬币(或Sm)。
2)解决方案包含至少一个 第m种硬币。
让数(S [] , M, N)是该函数来计算解的数目,则它可以表示为计数的总和(S [], M-1, N)和计数(S [],M,N-Sm)。

因此,这个问题具有最优子结构性质的问题。

2) 重叠子问题

下面是一个简单的递归实现硬币找零问题。遵循上面提到的递归结构。

#include<stdio.h>
int count( int S[], int m, int n )
{
    // 如果n为0,就找到了一个方案
    if (n == 0)
        return 1;
    if (n < 0)
        return 0;
    // 没有硬币可用了,也返回0
    if (m <=0 )
        return 0;
    // 按照上面的递归函数
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}

// 测试
int main()
{
    int i, j;
    int arr[] = {1, 2, 3};
    int m = sizeof(arr)/sizeof(arr[0]);
    printf("%d ", count(arr, m, 4));
    getchar();
    return 0;
}

应当指出的是,上述函数反复计算相同的子问题。见下面的递归树为S = {1,2,3},且n = 5。
的函数C({1},3)被调用两次。如果我们绘制完整的树,那么我们可以看到,有许多子问题被多次调用。

C() --> count()
                              C({1,2,3}, 5)                     
                           /                \
                         /                   \              
             C({1,2,3}, 2)                 C({1,2}, 5)
            /     \                        /         \
           /        \                     /           \
C({1,2,3}, -1)  C({1,2}, 2)        C({1,2}, 3)    C({1}, 5)
               /     \            /    \            /     \
             /        \          /      \          /       \
    C({1,2},0)  C({1},2)   C({1,2},1) C({1},3)    C({1}, 4)  C({}, 5)
                   / \      / \       / \        /     \    
                  /   \    /   \     /   \      /       \ 
                .      .  .     .   .     .   C({1}, 3) C({}, 4)
                                               /  \
                                              /    \  
                                             .      .

所以,硬币找零问题具有符合动态规划的两个重要属性像其他典型的动态规划(DP)的问题,可通过自下而上的方式打表,存储相同的子问题。当然上面的递归程序也可以改写成记忆化存储的方式来提高效率。

下面是动态规划的程序:

#include<stdio.h>

int count( int S[], int m, int n )
{
    int i, j, x, y;

    // 通过自下而上的方式打表我们需要n+1行
    // 最基本的情况是n=0
    int table[n+1][m];

    // 初始化n=0的情况 (参考上面的递归程序)
    for (i=0; i<m; i++)
        table[0][i] = 1;

    for (i = 1; i < n+1; i++)
    {
        for (j = 0; j < m; j++)
        {
            // 包括 S[j] 的方案数
            x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;

            // 不包括 S[j] 的方案数
            y = (j >= 1)? table[i][j-1]: 0;

            table[i][j] = x + y;
        }
    }
    return table[n][m-1];
}

// 测试
int main()
{
    int arr[] = {1, 2, 3};
    int m = sizeof(arr)/sizeof(arr[0]);
    int n = 4;
    printf(" %d ", count(arr, m, n));
    return 0;
}

时间复杂度:O(mn)

以下为上面程序的优化版本。这里所需要的辅助空间为O(n)。因为我们在打表时,本行只和上一行有关,类似01背包问题。

int count( int S[], int m, int n )
{
    int table[n+1];
    memset(table, 0, sizeof(table));
    //初始化基本情况
    table[0] = 1;

    for(int i=0; i<m; i++)
        for(int j=S[i]; j<=n; j++)
            table[j] += table[j-S[i]];

    return table[n];
}

参考:http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

http://www.algorithmist.com/index.php/Coin_Change


  1. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }

  2. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  3. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……