21xrx.com
2024-11-05 21:33:55 Tuesday
登录
文章检索 我的文章 写文章
C++贪心算法实现找零问题
2023-07-12 14:00:02 深夜i     --     --
C++ 贪心算法 找零问题 硬币 最少数量

在日常生活中,找零问题是一个非常常见的场景。假设某个人购买了一件商品,需要支付一定金额,但是该金额超过了实际商品价格,于是该人需要找回一定的零钱。如果这个人希望尽可能地少找钱,那么这就是一个经典的贪心算法问题。下面,我们以 C++ 代码的形式来实现找零问题的贪心算法。

假设顾客需要找回的零钱有以下几种面额:1 元,5 元,10 元和 50 元。我们需要编写一个函数来计算这个人最少需要找回多少钱。我们假定该函数的原型如下:


int getMinChange(int price, int paid);

参数 price 表示商品实际价格,paid 表示顾客实际支付的金额。函数返回值为顾客最少需要找回的钱数。

我们可以采用贪心策略来实现这个函数。具体的思路如下:

1. 初始化一个数组 change[],用来表示各种面额的零钱还有多少个。

2. 计算需要找回的钱数 changeNeeded = paid - price。

3. 从面额最大的零钱开始,计算该面额的零钱可以找几个。

4. 从面额次大的零钱开始,计算该面额的零钱可以找几个,直到找完所有的零钱。

5. 将所有的零钱数量相加,就是最少需要找回的钱数。

以下是完整的 C++ 代码实现:


#include <iostream>

using namespace std;

const int NUM_OF_COINS = 4;

const int COINS[] = 1;

int getMinChange(int price, int paid) {

  int change[NUM_OF_COINS] = {0};

  int changeNeeded = paid - price;

  int numCoins = 0;  // 记录找回的零钱数量

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

    // 计算该面额的零钱可以找几个

    while (changeNeeded >= COINS[i]) {

      changeNeeded -= COINS[i];

      change[i]++;

      numCoins++;

    }

  }

  return numCoins;

}

int main() {

  int price, paid;

  cout << "请输入商品实际价格:";

  cin >> price;

  cout << "请输入顾客实际支付的金额:";

  cin >> paid;

  int minChange = getMinChange(price, paid);

  cout << "最少需要找回 " << minChange << " 元零钱" << endl;

  return 0;

}

在函数内部,我们首先初始化了 change[] 数组,然后计算了需要找回的钱数 changeNeeded。接着,我们从面额最大的零钱开始循环,每次都计算该面额的零钱可以找几个。最后,我们将所有的零钱数量相加,就得到了最少需要找回的钱数。

在主函数中,我们先让用户输入商品实际价格和顾客实际支付的金额。然后,我们调用 getMinChange() 函数来计算最少需要找回多少钱。最后,我们输出计算结果。

这就是 C++ 贪心算法实现找零问题的示例。贪心算法在实际应用中具有广泛的用途,可以用来解决很多实际问题。在使用贪心算法时,需要确保问题具有贪心选择性质和最优子结构性质。如果这两个性质都满足,那么贪心算法就可以给出正确的最优解。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复