C++ 实现找零钱问题 |21xrx.com

C++ 实现找零钱问题

2023-06-29 05:06:20 深夜i -- --

C++ 零钱问题算法动态规划贪心算法

找零钱问题，是指一种常见的计算问题，即如何拆解一定金额的钞票和硬币来满足特定的金额需求。对于程序设计领域而言，找零钱问题常被用于教学和测试的范例，同时其解法也直接涉及程序设计中的算法和数据结构。

在 C++ 中，通过以下代码实现找零钱问题：


#include <vector>
#include <iostream>
using namespace std;
vector<int> change(int amount, vector<int>& coins) {
  vector<int> dp(amount + 1, amount + 1);
  dp[0] = 0;
  for(int i = 1; i <= amount; i++) {
    for(int j = 0; j < coins.size(); j++) {
      if (coins[j] <= i) {
        dp[i] = min(dp[i], dp[i - coins[j]] + 1);
      }
    }
  }
  return dp[amount] > amount ? vector<int> {-1} : vector<int> {dp[amount]};
}
int main() {
  int amount = 11;
  vector<int> coins = 2;
  vector<int> result = change(amount, coins);
  cout << result[0];
  return 0;
}

在上述代码中，我们通过 vector 存储硬币面值，dp 存储找零钱的结果。通过外层循环来逐个计算每个 amount 的结果，内层循环则是遍历硬币面值，根据当前计算的 amount 和硬币面值计算 dp 的值。

最后，我们可以通过 check 结果，如果 dp[amount] 大于 amount，则说明无法找零，返回 [-1]，否则返回 dp[amount]。在示例代码执行后，找零钱的结果是 3，即使用两个面值是 5 的硬币和一个面值为 1 的硬币来找零。

总之，找零钱问题在程序设计领域具有重要的意义，能够帮助人们更好地理解和掌握算法和数据结构的基本知识，让编程更加高效和准确。

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

下一篇: C++使用筛选法求解100以内的素数

评论区

()

相似文章