贪心算法解决找零钱问题

Dear 丶 2022-06-07 04:22 376阅读 0赞

**4.1 找零问题**  
问题描述：  
设有50、20、10、5、1、0.5、0.1等面额的零钱，顾 客购物花了n元，在支付（n / 100 + 1） \* 100元后，收银员应如何找 零，才能使找回的钱数最少。  
输入： n，表示顾客所花的钱数，最多包含一位小数。  
输出： 找回的零钱数。  
样例输入： 67.5 243  
样例输出： 5 4

//ACM贪心算法应用——找零问题
    #include <iostream>
    using namespace std;
    double MONEY_UNIT[7] = {
       50, 20, 10, 5, 1, 0.5, 0.1};    //钱的所有面额
    
    int main()
    {
        double consumeMoney = 0;                            //消费的金额
        cin >> consumeMoney;
        double realGiveMoney = 0;                           //实际给的钱
        realGiveMoney = (int)(consumeMoney / 100 + 1) * 100;//通过int的自动舍去小数位来计算实际给的钱数
        double shouldRevMoney = 0;                          //应该找回的零钱
        shouldRevMoney = realGiveMoney - consumeMoney;
        //贪心算法实现——局部最优解
        int revMoneyAmount = 0;
        for (int i = 0; i < 7; i ++) {
            if (MONEY_UNIT[i] <= shouldRevMoney) {
                shouldRevMoney -= MONEY_UNIT[i];
                i--;                                        //继续测试此面额的money是否满足
                revMoneyAmount++;                           //找回零钱张数加1
            }
            if (!shouldRevMoney) {
                break;
            }
        }
        cout << "找回的零钱最少张数为 ：";
        cout << revMoneyAmount << endl;
    
        system("pause");
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，376人围观）

还没有评论，来说两句吧...

相关阅读

相关 Cplusplus利用贪心算法实现找零钱问题

贪心算法是一种常用的求解找零钱问题的方法。在 C++ 中，可以先将所有可用的硬币按面额从大到小排序。然后，每次从大到小遍历这些硬币，并在能使用时尽量多地使用较大的硬币。这样

柔光的暖阳◎/ 2024年03月26日 09:08/ 0 赞/ 17 阅读

相关 1259: 找零钱

1259: 找零钱时间限制: 1 Sec 内存限制: 128 MB 提交: 73 解决: 55 您该题的状态：已完成 \[[提交][Link 1]\]\[[

亦凉/ 2024年02月18日 22:04/ 0 赞/ 12 阅读

相关 C语言贪心算法，关于零钱取整问题

include<stdio.h> void greedyMoney(int m[],int k,int n); int main(void) {

╰+哭是因爲堅強的太久メ/ 2022年08月19日 12:12/ 0 赞/ 129 阅读

相关找零钱

找零钱 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述我们知道人民币有1、2、5、

╰半橙微兮°/ 2022年08月18日 02:23/ 0 赞/ 120 阅读

相关贪心算法解决活动安排问题

4.2 活动安排问题设有n个活动的集合E=\{1, 2, …, n\}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个

青旅半醒/ 2022年06月07日 04:35/ 0 赞/ 276 阅读

相关贪心算法解决找零钱问题

4.1 找零问题问题描述：设有50、20、10、5、1、0.5、0.1等面额的零钱，顾客购物花了n元，在支付（n / 100 + 1） \ 100元后，收银员应如

Dear 丶/ 2022年06月07日 04:22/ 0 赞/ 377 阅读

相关动态规划法（二）找零钱问题

本次博客尝试以storyline的方式来写作，如有不足之处，还请多多包涵~~ 问题的诞生我们故事的主人公叫做丁丁，他是一个十几岁的小男孩，机智聪颖，是某某杂货

ゝ一纸荒年。/ 2022年05月24日 13:52/ 0 赞/ 155 阅读

相关贪心算法之钱币找零问题

贪心算法一、基本概念：所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上

青旅半醒/ 2022年05月18日 23:59/ 0 赞/ 344 阅读

相关约瑟夫问题，找零钱问题

假设拿着山芋的孩子在队列的前面。当拿到山芋的时候，这个孩子将先出列再入队列，把他放在队列的最后。经过 num 次的出队入队后，前面的孩子将被永久移除队列。并且另一个周期开始，继

刺骨的言语ヽ痛彻心扉/ 2022年04月24日 15:52/ 0 赞/ 113 阅读

相关贪心算法 - 钱币找零问题

这个问题在我们的日常生活中就更加普遍了。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱

深藏阁楼爱情的钟/ 2022年02月21日 07:10/ 0 赞/ 217 阅读