[每日一道小算法（一）][贪心算法] 硬币问题

布满荆棘的人生 2023-06-28 08:55 49阅读 0赞

前言：  
今天看到了一个有意思的算法题，准备在这里记录一下，方便以后查阅。自己的算法能力挺差的，准备开个专栏专门写算法，每天至少一篇，提升一下自己算法的能力，就从这一篇开始吧。打卡第一天。

#### 题目描述 ####

一元硬币，五元硬币，十元硬币，五十元硬币，壹佰元硬币，五百元硬币，分别有C1，C5，C10，C50，C100，C500枚。我们想要以用可能少数量的硬币帮忙支付A。到底需要出几枚硬币呢？另外假设这种付款方式至少存在一种。  
0<= C <= 10^9  
0<= A <= 10^9

输入样例：  
c1=3 c5=2 c10 =1 c50=3 c100=0 c500=2 A=620

输出：  
6

#### 解题分析 ####

我们先看我们要解决的问题是什么？  
也就是求出支付A需要几枚硬币的最少方案。既然是最少的方案，那么我们就要先用醉倒币值去支付，依次减少，直到最后支付完成。这也就是贪心算法，一直用最大的币值去支付，直到支付完成。  
这么一分析，这道题还是挺简单的嘛，下面我们开始写代码，我本次使用的java。

#### 代码样例 ####

public static int getMin(int a,int b)
        { 
            return (a>b)?b:a;
        }
    
        public static void main(String[] args)
        { 
            int[] num = { 1,5,10,50,100,500};
            int[] count = new int[6];
            int ans=0;
            Scanner scanner= new Scanner(System.in);
    
            int a = scanner.nextInt();
    
            for(int i=0;i<6;i++)
            { 
                count[i] = scanner.nextInt();
            }
            for(int j=5;j>=0;j--)
            { 
                int t = getMin(a/num[j],count[j]);
                a -=num[j]*t;
                ans +=t;
                if(a==0)
                { 
                    break;
                }
            }
            System.out.println("总共花硬币枚数： "+ans);
    
        }

至此这道题就解决完成了。大功告成！！！！！！！