三种硬币1角五角一元,凑够二元六角,设计一个算法求有哪些组合方式,用c++语言
时间: 2024-09-29 12:02:05 浏览: 37
这是一个经典的动态规划问题,可以使用回溯法或者递归的方式来解决。以下是使用C++的一个简单示例:
```cpp
#include <iostream>
#include <vector>
std::vector<std::vector<int>> coins = {1, 5, 10}; // 1角、5角、1元硬币
bool canMake(int target, int remaining) {
if (remaining == 0 && target <= 10) { // 到达目标金额,且不超过10元(因为题目只提到凑到二元六角)
return true;
}
if (remaining < 0 || target < 0) { // 越界条件
return false;
}
for (int coin : coins) {
if (remaining >= coin) { // 如果剩余金额足够支付当前面额
if (canMake(target - coin, remaining - coin)) { // 尝试用这个硬币,并继续寻找其他组合
return true;
}
}
}
return false; // 没有找到可行组合,返回false
}
void findCombinations(int target, int current, std::vector<int>& result) {
if (target == 0) {
result.push_back(current);
return;
}
for (int coin : coins) {
if (target >= coin && canMake(target - coin, current + coin)) {
result.push_back(current + coin);
findCombinations(target - coin, current + coin, result); // 继续搜索余下的组合
}
}
}
int main() {
int target = 26; // 目标金额
std::vector<int> combinationResult;
if (canMake(target, 0)) {
findCombinations(target, 0, combinationResult);
for (const auto& combo : combinationResult) {
std::cout << "组合: " << combo << " 元" << std::endl;
}
} else {
std::cout << "无法凑出指定金额的组合" << std::endl;
}
return 0;
}
```
阅读全文