淘先锋技术网

首页 1 2 3 4 5 6 7

相关问题1:https://blog.csdn.net/jiyanfeng1/article/details/8079530

问题:

假设有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];
}