算法——硬币选择问题（dp、贪心）

绝地灬酷狼 2022-06-05 23:45 216阅读 0赞

`本题来自2015级算法第四次上机`

# `A` 怠惰的王木木Ⅱ #

时间限制：1000ms 内存限制：65536kb

通过率：1/165 `(0.61%)` 正确率：1/416 `(0.24%)`

## 题目描述 ##

王木木又到Magry家里打工了，这次的工作是找零钱。

作为一名合格的收银员，必须快速的计算价格并找钱给顾客。王木木很懒所以找钱是都希望用尽可能少的纸币。现在，假设收银台有面值为1元、5元、10元、20元、50元、100元的纸币各Ai、Bi、Ci、Di、Ei、Fi 张，需要找的钱的数额为X元，那最少需要多少张纸币呢？假定至少存在一种找钱方案。

## 输入 ##

多组测试数据，对于每组数据，输入两行，

第一行为6个整数，分别代表1元、5元、10元、20元、50元、100元的纸币张数

第二行为一个正整数A，代表需要支付的钱数。所有整数Intager都在 0≤Intager≤1000  范围内，1≤A≤1000 。

## 输出 ##

对于每组数据，输出一行，为最少的纸币张数

## 输入样例 ##

1 2 3 4 5 6
    176

## 输出样例 ##

之前练习赛做过一道硬币找零问题，它的面值是1,5,10,50,100,500，完全的贪心题型，为什么这里可以用贪心，我们知道，贪心是有条件的，在本题中贪心策略的前提非常简单，即大额硬币必须是所有面值小于它的硬币的面值倍数。原因：[http://blog.csdn.net/hwdopra/article/details/6318746][http_blog.csdn.net_hwdopra_article_details_6318746]。

那么本题呢？面值分别是1,5,10,20,50,100，这就不符合之前贪心的使用条件，比如输入（10,0,0,3,1,0,60,），60=50\*1+10\*1，60=20\*3，就本题来说，要解决这个问题还是不难的，对50面值的特殊对待，我就从0~coinNum\[4\]循环一边，其他的依然贪心处理。这个问题就解决了，代码如下（DP内为动态规划做法）。

//
    //  main.cpp
    //  怠惰的王木木Ⅱ
    //
    //  Created by Angus on 2017/10/24. 
    //  Copyright © 2017年 Angus. All rights reserved.
    //
    
    
    #include <iostream>
    #include <cmath>
    //#define DP
    
    using namespace std;
    
    #ifdef DP
    #define INF 0x3f3f3f3f
    int V[10] = {0, 1, 5, 10, 20, 50, 100};//硬币面值
    long long C[10];//硬币对应的个数
    long long dp[1005][100005];
    long long A;
    void solve()
    {
        long long n = 6;
        for(int i = 1;i <= n;i++)//初始化
        {
            for(int j = 0;j <= A;j++)
            {
                if(j == 0)//找出0块钱
                    dp[i][j] = 0;
                else if(i == 1)//最小面值初始化
                {
                    if(j % V[i] == 0 && j / V[i] <= C[i])
                        dp[1][j] = j / V[i];
                    else
                        dp[1][j] = INF;
                }
                else
                    dp[i][j] = INF;
            }
        }
        
        for(int i = 2;i <= n;i++)//构造dp数组
        {
            for(int j = 1;j <= A;j++)
            {
                for(int k = 0;k <= C[i];k++)
                {
                    if(dp[i][j] > dp[i-1][j - k * V[i]] + k && j - k * V[i] >= 0)
                        dp[i][j] = dp[i-1][j - k * V[i]] + k;
                }
            }
        }
    //    for (int i = 0; i <= n; i++)
    //    {
    //        for (int j = 0; j <= A; j++)
    //        {
    //            if(dp[i][j] == INF)
    //                printf("INF ");
    //            else
    //                printf("%lld ",dp[i][j]);
    //        }
    //        printf("\n");
    //    }
        if(dp[n][A] != INF)
            printf("%lld\n",dp[n][A]);
        else
            printf("error\n");
    }
    
    int main()
    {
        while (~scanf("%lld%lld%lld%lld%lld%lld%lld",&C[1],&C[2],&C[3],&C[4],&C[5],&C[6],&A))
        {
            solve();
        }
        return 0;
    }
    #endif
    
    //贪心算法
    int V[6] = {1, 5, 10, 20, 50, 100};//硬币面值
    long long C[6];//硬币对应的个数
    long long A, B;
    
    void Solve()//求最小需要的硬币数
    {
        long long ans1 = 0, ans2 = 9999;
        long long t = min(A / V[5], C[5]);
        A -=  V[5] * t;
        ans1 = t;
        B = A;
        for (int i = 0; i <= min(B / V[4], C[4]); i++)
        {
            A = B;
            A -=  V[4] * i;
            long long tmp = 0;
            for(int j = 3; j >= 0; j--)
            {
                long long k = min(A / V[j], C[j]);
                A -=  V[j] * k;
                tmp += k;
                //printf("%lld\n",k);
            }
            if(A == 0)
                ans2 = min(ans2,tmp + i);
        }
        cout << ans1 + ans2 <<endl;
    }
    
    int main()
    {
        while (~scanf("%lld%lld%lld%lld%lld%lld%lld",&C[0],&C[1],&C[2],&C[3],&C[4],&C[5],&A))
        {
            Solve();
        }
        return 0;
    }

但是，不能满足于此，如果给任意面值任意数量呢？我们知道，贪心可以说是动态规划的一小类特殊问题的解法，所以这里要用动态规划。

问题定义：dp\[i\]\[j\] 表示当前i种硬币找j块钱最少硬币数，dp\[n\]\[m\] 是我们要求的最终结果。

那么如何把这个大问题分解成小的同类问题？dp\[i\]\[j\]=min\{dp\[i\]\[j\],dp\[i-1\]\[j–k\*CoinValue\[i\]\]+k\}，条件k<\[0, coinNum\[i\]\]&&j-k\* coinValue\[i\] >= 0，即对每一个硬币都遍历一次。

举个例子，coinValue\[\]= \{1，2，5\}，每一种硬币的数量是有限的，分别是CoinNum\[\]=\{3, 3, 3\}，给定一个数值m=18， dp\[3\]\[ 18\] = min\{dp\[2\]\[18\] + 0,dp\[2\]\[18-1\*5\]+1, dp\[2\]\[18-2\*5\] + 2,dp\[2\]\[18- 3\* 5\] + 3\}，也就是说dp \[3\]\[18\]可以分解为当对于5块值得硬币选0个，选1个，选2个，选3个之后的子问题，当选完5这种硬币时，接下来只有1块和2块的硬币可选， 于是子问题就变成dp\[2\]\[18\],dp\[2\]\[13\],dp\[2\]\[8\], dp\[2\]\[3\]。

注：参考代码二是普遍情况：求n中面值找出m零钱的最小硬币数，非AC代码，可做模板。

参考资料： [http://blog.csdn.net/suwei19870312/article/details/9296415][http_blog.csdn.net_suwei19870312_article_details_9296415]。

#include<cstdio>
    #define INF 0x3f3f3f3f
    
    int dp[11][20002];//dp[i][j]前i种硬币找j块钱最少硬币数
    int coinValue[11],coinNum[11];//面值及其数量
    
    int main()
    {
        int i,j,k,n,m;//n种面值，找出m块零钱
        while(~scanf("%d",&n))
        {
            for(i=1;i<=n;i++)//按面值升序输入
                scanf("%d%d",&coinValue[i],&coinNum[i]);
            
            scanf("%d",&m);
            
            for(i=1;i<=n;i++)//初始化
            {
                for(j=0;j<=m;j++)
                {
                    if(j==0)//找出0块钱
                        dp[i][j]=0;
                    else if(i==1)//最小面值初始化
                    {
                        if(j%coinValue[i]==0&&j/coinValue[i]<=coinNum[i])
                            dp[1][j]=j/coinValue[i];
                        else
                            dp[1][j]=INF;
                    }
                    else
                        dp[i][j]=INF;
                }
            }
            
            for(i=2;i<=n;i++)//构造dp数组
                for(j=1;j<=m;j++)
                    for(k=0;k<=coinNum[i];k++)
                        if(dp[i][j]>(dp[i-1][j-k*coinValue[i]]+k)&&(j-k*coinValue[i])>=0)
                            dp[i][j]=dp[i-1][j-k*coinValue[i]]+k;
    //        for (int i = 0; i <= n; i++)
    //        {
    //            for (int j = 0; j <= m; j++)
    //            {
    //                if(dp[i][j] == INF)
    //                    printf("INF ");
    //                else
    //                    printf("%d ",dp[i][j]);
    //            }
    //            printf("\n");
    //        }
            if(dp[n][m]!=INF)
                printf("%d\n",dp[n][m]);
            else
                printf("-1\n");
        }
        return 0;
    }

问题拓展

硬币组合问题

假设现有3种硬币，\{1,2,5\}, 但是每种硬币的个数没有限制，可以是无限，现在问要筹成18， 有多少种组合方式？

思路： 动态规划。

问题定义：

dp\[n\]\[m\]表示当目标值为n, 有m种硬币可选的时候的组合数，同样，dp\[18\]\[3\]是我们要求的最终结果。

同样,dp\[n\]\[m\] = sum\{ dp\[n – i\*CoinValue\[m\]\]\[m-1\]\} 条件 n-i\*CoinValue\[m\] >=0

那么dp\[18\]\[3\] =dp\[18\]\[2\] + dp\[13\]\[2\] + dp\[8\]\[2\] + dp\[3\]\[2\].

也就是说dp\[18\]\[3\]可以分解为当对于5分值得硬币选0个，选1个，选2，选3个之后的子问题，当选完5这种硬币时，接下来只有1分和2分的硬币可选， 于是子问题就变成为dp\[18\]\[2\],dp\[13\]\[2\], dp\[8\]\[2\], dp\[3\]\[2\].

代码：[http://blog.sunchangming.com/post/54899551762][http_blog.sunchangming.com_post_54899551762]

[http_blog.csdn.net_hwdopra_article_details_6318746]: http://blog.csdn.net/hwdopra/article/details/6318746
[http_blog.csdn.net_suwei19870312_article_details_9296415]: http://blog.csdn.net/suwei19870312/article/details/9296415
[http_blog.sunchangming.com_post_54899551762]: http://blog.sunchangming.com/post/54899551762