你好,游客 登录 注册 搜索
背景:
阅读新闻

硬币找零问题之动态规划

[日期:2017-06-12] 来源:Linux社区  作者:gaorong [字体: ]

今天我们看一下动态规划的硬币找零问题,主要通过一系列编程题分析动态规划的规律,只要掌握这一规律,许多动态规划的相关问题都可以类比得到。

题目1:给定数组arr,arr中所有的值都是正数且不重复。每个值代表一种面值的货币,每种面值的货币可以使用任意张,再给定一个整数aim代表要找的钱数,求组成aim的最少货币数。

举例:

arr[5,2,3],aim=20。  4张5元可以组成20元,其他的找钱方案都要使用更多张的货币,所以返回4。

题解:

一眼看去这道题好像可以用贪心算法可解,但是仔细分析发现有些值是不可以的,例如arr[1,3,4],aim=6 :用贪心算法算最少钱数为3 (4+1+1),但是我们可以明显的发现用两张3元的就够了,所以用贪心算法不可解。

其实这是一道经典的动态规划方法,我们可以构造一个dp数组,如果arr的长度为N,则dp数组的行数为N,列数为aim+1,dp[i][j] 的含义是:在可以任意使用arr[0..i]货币的情况下,组成j所需要的最小张数。

明白以上定义后我们初始化第一行与第一列,第一行dp[0][0..aim]中每一个元素dp[0][j]表示用arr[0]货币找开面额 j所需要的最少货币数,此时我们只能选取arr[0]这一张货币,所以只有arr[0]的整数倍的面额钱才可以找开,例如当arr[0]=3,aim=10时,只能找开3,6,9的货币,而其他面额的则无法找开,所以将arr[0][3,6,9]初始化为1,2,3 除此之外其他值初始化为整形int的最大值INT_MAX表示无法找开。对于第一列dp[0..n][0] 中的每一个元素dp[i][0]表示用arr[i]组成面额为0的钱的最少货币数,完全不需要任何货币,直接初始化为0即可。

对于剩下的任意dp[i][j],我们依次从左到右,从上到下计算,dp[i][j]的值可能来自下面:

  • 完全不使用当前货币arr[i]的情况下的最少张数,即dp[i-1][j]的值
  • 只使用1张当前货币arr[i]的情况下的最少张数,即dp[i-1][j-arr[i]]+1
  • 只使用2张当前货币arr[i]的情况下的最少张数,即dp[i-1][j-2*arr[i]]+2
  • 只使用3张当前货币arr[i]的情况下的最少张数,即dp[i-1][j-3*arr[i]]+3
  • …..

以上所有情况中,最终取张数最小的,即dp[i][j] = min( dp[i-1][j-k*arr[i]]+k )( k>=0 )

=>dp[i][j] = min{ dp[i-1][j], min{ dp[i-1][j-x*arr[i]]+x (1<=x) } }    令x = y+1

=>dp[i][j] = min{ dp[i-1][j], min{ dp[i-1][j-arr[i]-y*arr[i]+y+1 (0<=y) ] } }

又有 min{ dp[i-1][j-arr[i]-y*arr[i]+y (0<=y) ] } => dp[i][ j-arr[i] ] ,所以,最终有:dp[i][j] = min{ dp[i-1][j], dp[i][j-arr[i]]+1 }。如果j-arr[i] < 0,即发生了越界,说明arr[i]太大了,用一张都会超过钱数j,此时dp[i][j] = dp[i-1][j]。

int coinChange(vector<int>& arr, int aim) {
        int len = arr.size();
        vector<vector<int>> dp(len, vector<int>(aim+1,0));

     
        for(int i=1; i<=aim; i++){
            dp[0][i] = INT_MAX;
            if( i>=arr[0] && dp[0][i-arr[0]] !=INT_MAX ){
                dp[0][i] = dp[0][i-arr[0]]+1;
            }
        }
     
        for(int i=1; i<len; i++){
            for(int j=1; j<=aim; j++){
                int left = INT_MAX;
                if( j>=arr[i] && dp[i][j-arr[i]] != INT_MAX ){
                    left=dp[i][j-arr[i]]+1;
                }
                dp[i][j] = min( dp[i-1][j], left );
            }
        }   

        return dp[len-1][aim]==INT_MAX ? -1 : dp[len-1][aim];
    }

参见leetcode : 322. Coin Change

上面的问题还可以进行空间压缩,此处不再赘述。

上面说贪心算法不可解其实面值在部分情况下可以用贪心算法解决,如果可换的硬币的单位是 c 的幂,也就是 c0,c1,... ,ck ,其中整数 c>1,k>=1,一定可以用贪心算法,或者某些情况比如,面值为1,5,10,20,50,100时,贪心找零也一定有最优解。参见《挑战程序设计竞赛》第二版2.2.1节。

题目2: 给定数组arr,arr中所有的值都为正数,每个值仅代表一张钱的面值,再给定一个整数aim代表要找的钱数,求组成aim的最小货币数。

题解: 相对于上一题,这道题的arr中的钱只有一张,而不是任意多张,构造dp数组的含义也同上,但是此时略有不同,

dp第一行dp[0][0..aim]的值表示只使用一张arr[0]货币的情况下,找某个钱数的最小张数。比如arr[0]=2,那么能找开的钱数仅为2, 所以令dp[0][2]=1。因为只有一张钱,所以其他位置所代表的钱数一律找不开,一律设为INT_MAX。第一列dp[0…N-1]表示找的钱数为0时需要的最少张数,钱数为0时完全不需要任何货币,所以全设为0即可。

剩下的位置从左到右,从上到下计算,dp[i][j]可能的值来自于以下两种情况

1.dp[i][j]的值代表在可以任意使用arr[0..i-1]货币的情况下,组成j所需要的最小张数。可以任意使用arr[0..i]货币的情况当然包括不使用arr[i]的货币,而只使用任意arr[0..j-1]货币的情况,所以dp[i][j]的值可能为dp[i-1][j]。

2.因为arr[i]只有一张不能重复使用,所以我们考虑dp[i-1][j-arr[i]]的值,这个值代表在可以任意使用arr[0..i-1]货币的情况下,组成j-arr[i]所需的最小张数。从钱数为j-arr[i]到钱数j,只用在加上这张arr[i]即可。所以dp[i][j]的值可能等于do[i-1][j-arr[i]]+1。

3.如果dp[i-1][j-arr[i]]中j-arr[i] < 0,也就是位置越界了,说明arr[i]太大了,只用一张就会超过钱数j,令dp[i][j]=dp[i-1][j]即可。

int coinChange(vector<int>& arr, int aim) {
        int len = arr.size();
        vector<vector<int>> dp(len, vector<int>(aim+1,0));
     
        for(int i=1; i<=aim; i++){
            dp[0][i] = INT_MAX;
        }

        if ( arr[0] <= aim ){
            dp[0][arr[0]] = 1;
        }
   
        for(int i=1; i<len; i++){
            for(int j=1; j<=aim; j++){
                int leftup = INT_MAX;
                if( j>=arr[i] && dp[i][j-arr[i]] != INT_MAX ){
                    leftup=dp[i-1][j-arr[i]]+1;
                }
                dp[i][j] = min( dp[i-1][j], leftup );
            }
        }
   
        return dp[len-1][aim]==INT_MAX ? -1 : dp[len-1][aim];
 }

题目3:给定数组arr,arr中所有的值都为正数且重复。每个值代表一种面值的货币,每种面值的货币可以使用任意张,再给定一个整数aim代表要找的钱数,求换钱有多少种方法。

题解: 类比题目1,每个面值的钱可以使用任意多次,我们可以构造一个dp数组,如dp数组的行数为N,列数为aim+1,dp[i][j] 的含义是:在可以任意使用arr[0..i]货币的情况下,组成钱数j有多少张方法。。

第一行dp[0][0..aim]中每一个元素dp[0][j]表示用arr[0]货币找开面额 j的方法,此时我们只能选取arr[0]这一张货币,所以只有arr[0]的整数倍的面额钱才可以找开,例如当arr[0]=3,aim=10时,只能找开3,6,9的货币,且只有一种方法即只是用arr[0],而其他面额的则无法找开,所以将arr[0][3,6,9]初始化为1 除此之外其他值初始化为0表示无法找开。对于第一列dp[0..n][0] 中的每一个元素dp[i][0]表示用arr[i]组成面额为0的钱的最少货币数,完全不需要任何货币,即一种方法,初始化为1。

对于剩下的任意dp[i][j],我们依次从左到右,从上到下计算,dp[i][j]的值下面的方法数的和:

•完全不用arr[i]的货币,只使用arr[0..i-1]货币时,方法数为dp[i-1][j]

•用1张arr[i]货币,剩下的钱用arr[0..i-1]货币组成时,方法数为dp[i-1][j-arr[i]]

•用2张arr[i]货币,剩下的钱用arr[0..i-1]货币组成时,方法数为dp[i-1][j-2*arr[i]]

•…

•用k张arr[i]货币,剩下的钱用arr[0..i-1]货币组成时,方法数为dp[i-1][j-k*arr[i]]

其实从第二种情况到第k种情况方法的累加值其实就是dp[i][j-arr[i]]的值,所以dp[i][j] = dp[i-1][j] + dp[i][j-arr[i]] 。

int countWays(vector<int> arr, int n, int aim) {
        vector<vector<int>> dp( n, vector<int>(aim+1,0) );
        for(int j=0; arr[0]*j<=aim; j++){
            dp[0][arr[0]*j] = 1;
        } 

        for (int i = 1; i<n; i++){
            dp[i][0] = 1;

            for (int j = 1; j <= aim; j++){
                if (j - arr[i] >= 0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - arr[i]];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[n - 1][aim];
    }

题目4:给定数组arr,arr中所有的值都为正数且重复。每个值代表一张钱的面值再给定一个整数aim代表要找的钱数,求换钱有多少种方法。

题解:类比题目2,也是每个钱只能使用一次,此处不做解释

给出一道例题及答案:

例题:

给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。当两种选取方案有一���数字的下标不一样,我们就认为是不同的组成方案。

输入描述:  输入为两行: 第一行为两个正整数n(1 ≤ n ≤ 1000),sum(1 ≤ sum ≤ 1000),第二行为n个正整数A[i](32位整数),以空格隔开。

输出描述:  输出所求的方案数

输入例子:

5 15

5 5 10 2 3

输出例子:

4

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;

int main(){
    long long a, sum;
    while (cin >> a >> sum){
        vector<int> vec(a);
        for (int i = 0; i<a; i++)  cin >> vec[i];

        vector<vector<long>> dp(a, vector<long>(sum + 1, 0));
        for (int i = 0; i < a; i++){
            dp[i][0] = 1;
        }

        if (sum >= vec[0]){
            dp[0][vec[0]] = 1;
        }

        for (int i = 1; i<a; i++){
            for (int j = 1; j <= sum; j++){
                if (j >= vec[i]){
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - vec[i]];
                }
                else
                {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        cout << dp[a - 1][sum] << endl;
    }
}                                   

进一步的优化交给读者自己思考咯。

本文永久更新链接地址http://www.linuxidc.com/Linux/2017-06/144657.htm

linux
相关资讯       动态规划  硬币找零问题 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款