用c++编写手里有不限数量的面值a元的金币和面值b元的金币,请问可以用金币刚好凑出总价c元吗
时间: 2024-10-09 15:02:14 浏览: 9
在 C++ 中,解决这个问题通常涉及到动态规划或者回溯算法,因为我们需要检查所有可能的组合是否能够凑出给定的目标金额 `c`。这里我们可以使用递归来实现这个思路:
```cpp
#include <iostream>
#include <vector>
bool canMakeChange(int c, std::vector<int>& coins, int a, int b) {
// 如果目标金额小于0,无法凑够,返回false
if (c < 0)
return false;
// 当前目标金额为0时,表示已经成功凑够,返回true
if (c == 0)
return true;
// 检查用面值a的金币凑
if (coins[a - 1] && canMakeChange(c - a, coins, a, b))
return true;
// 检查用面值b的金币凑,并考虑剩余部分
if (coins[b - 1] && canMakeChange(c - b, coins, a, b))
return true;
// 如果这两种都无法凑成,返回false
return false;
}
int main() {
int total = c; // 总价c
std::vector<int> coins = {a, b}; // 面值列表{a, b}
// ... 这里应该填充金币面值的具体数值
if (canMakeChange(total, coins, a, b))
std::cout << "可以凑出总价" << total << "元";
else
std::cout << "无法凑出总价" << total << "元";