C++贪心算法：找零问题 |21xrx.com

C++贪心算法：找零问题

2023-06-24 01:11:36 深夜i -- --

C++ 贪心算法找零问题

C++贪心算法是一种经典的算法，可以用于解决各种实际问题。其中一个常见的问题就是找零问题。在每天的生活中，我们都会遇到找零的情况，这时候就需要运用贪心算法来解决。

找零问题的本质就是找出一些数字，使得它们的和恰好等于要找的数目。举个例子，当我们在商店购物时，购买了一些商品，支付了一定的金额，需要收回一定的零钱。此时，我们需要找出一些纸币和硬币，使得它们的总和等于我们需要找回的零钱。如果我们使用贪心算法来解决这个问题，那么我们就要找到一种方案，每一步都是选取当前可选的最大值。

以下是一个C++代码实现的例子：


#include <iostream>
using namespace std;
int main() {
  int N;
  int coins[] = 20;
  int ans[6] = { 0 };
  cin >> N;
  for (int i = 0; i < 6; i++) {
    if (N >= coins[i]) {
      ans[i] = N / coins[i];
      N -= ans[i] * coins[i];
    }
  }
  for (int i = 0; i < 6; i++) {
    cout << coins[i] << "x" << ans[i] << endl;
  }
  return 0;
}

在上面的代码中，我们使用了一个`coins`数组来表示我们可以选用的纸币和硬币。在每次循环中，我们检查当前需要找的钱是否大于当前最大可选的钱数，如果是，则选取当前最大的钱数，将选用的数量存储在`ans`数组中，并更新需要找的零钱总数。最后，我们只需要输出选出的每种纸币和硬币的数量即可。

通过这种C++贪心算法的实现，我们可以简单、快速地解决找零问题，提高我们的生活品质。

上一篇: idea打包java可执行jar包

下一篇: 如何在C++中退出循环语句？

评论区

()

相似文章