C++ 贪心算法求解找零钱问题 |21xrx.com

C++ 贪心算法求解找零钱问题

2023-07-05 06:38:16 深夜i -- --

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

在日常生活中，找零钱问题是我们经常会遇到的。如果没有合适的解决方法，就有可能会找错零钱，甚至出现零钱不够的情况。针对这个问题，我们可以使用贪心算法来求解找零钱问题。

首先，什么是贪心算法？贪心算法是一种解决问题的策略，它总是选择当前看起来最好的解决方案，而不考虑全局的结果。在找零钱问题中，我们可以采取以下贪心策略：

假设我们要找36元的零钱，我们可以先从纸币面值最大的开始找，也就是从100元开始找，如果100元无法找完，再从次大的50元开始找，以此类推，直到找完36元为止。

具体的实现过程如下：

1. 定义一个数组 coin[] 来存储所有可用的纸币面额，且该数组必须从大到小排序。

2. 将需要找的零钱 total 记录下来。

3. 定义一个 int 类型的变量 sum，用来记录已经找到的零钱总数。

4. 遍历数组 coin[]，对于每一种纸币面额，如果该面额小于等于未找到的零钱 total，就用 total 除以该面额得到可以找零的数量，然后累加到 sum 中，同时将 total 减去已经找到的零钱数。

5. 当 sum 等于 total 时，找零钱过程结束。

下面是具体的 C++ 代码实现：


#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  int coin[] = 10;
  int total,sum=0;
  cin>>total;
  for(int i=0;i<6;i++){
    int count=total/coin[i];
    sum+=count;
    total-=count*coin[i];
    if(total==0) break;
  }
  cout<<sum<<endl;
  return 0;
}

使用贪心算法求解找零钱问题的时间复杂度为 O(n)，因此具有快速的求解速度。但是贪心算法是不完备的，不能保证解决方案一定是最优的。在面对一些特殊情况时，可能会得出错误的结果。因此，在使用贪心算法之前，我们需要考虑问题的性质和特殊情况，以保证算法的正确性。

总之，贪心算法是一种高效的解决找零钱问题的算法，它的实现简单，但要注意问题的特殊情况，才能得到正确的结果。

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

下一篇: C++感叹号是什么意思？

评论区

()

相似文章