c语言贪心算法零钱问题,贪心算法(2)——找零钱问题

72 阅读 0 评论 48 点赞

我是靠谱客的博主贪玩黄豆，最近开发中收集的这篇文章主要介绍c语言贪心算法零钱问题,贪心算法(2)——找零钱问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

一、找零钱问题

例题1：

有 1 元，5元，10元，20元，100元，200元的钞票无穷多张。现在使用这些钞票支付X元，最少需要多少张钞票。

X = 628

最佳支付方法：

3张200块的，1张20块的，1张5块的，3张1块的

共需3+1+1+3 = 8张

直觉告诉我们:尽可能多的使用面值较大的钞票!

贪心法: 遵循某种规律，不断贪心的选取当前最优策略的算法设计方法。

分析：面额为1元、5元、10元、20元、100元、200元，任意面额是比自己小的面额的倍数关系。所以当使用一张较大面额钞票时，若用较小面额钞票替换，一定需要更多的其他面额的钞票!

代码实现：

#include

using namespace std;

int main(){

const int RMB[]= {200,100,20,10,5,1};

const int NUM = 6;//6种面值

int X = 628;

int count = 0;

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

int use = X / RMB[i];需要面额为RMB[i]的use张

count + = use；

X = X -RMB[i] * use;

printf("需要面额为%d 的%d张

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。