最少硬币问题

核心算法

    贪心。

问题描述

     

    有1元、5元、10元、50元、100元、500元的硬币各C1、C5、C10、C50、C100、C500枚。现在用这些硬币来支付A元，最少需要多少枚硬币？假设本题至少存在一种支付方案。

问题分析

     

    这道题的核心思想很简单，面对当前金额如果可以用较大面值的硬币来支付的话，当然要用面值大的支付，但是本题又多了一条限制，每种硬币的数量是一定的，所以这就需要做一个比较。（待支付金额/较大面值）和（较大面值硬币的数量）两者的较小值是我们要选取的数量。

解题步骤

     

输入

按照题意进行输入

支付

优先使用面值较大的硬币进行支付

结束

支付完成

输出

输出选择的总个数

结束

解题步骤

    

//C++

#include<cstdio>

#include<algorithm>

using namespacestd;

const int v[6] ={1,5,10,50,100,500}; //储存硬币的面值

int a,c[6]; //c[0]= C1，c[1] = C5,c[2] = C10,... 

int main() {

    scanf('%d',&a); //输入需支付的金额

    for(int i = 0; i < 6; i++) {

       scanf('%d',&c[i]); //依次输入C1、C5、C10、C50、C100、C500

    }

    int ans = 0;

    for(int i = 5; i >= 0; i--) { //尽可能取大的面值

       int temp = min(c[i],a/v[i]); //取'当前面值硬币数量'和

//'待支付金额/面值'的较小值

       ans += temp; //结果加上取走的张数

       a -= temp*v[i]; //待支付金额减去这一轮支付的金额

    }

    printf('%d\n',ans); //输出答案

    return 0;

}

题目推荐

     

    设有n种硬币，要用他们来支付m元。

    第一种硬币的面值是V1、有C1张；第二种硬币的面值是V2、有C2张；...... 第n种硬币的面值是Vn、有Cn张。

    求最少需要多少枚硬币来支付m元。如果无法支付则输出'-1'。