2024年5月1日发(作者：)
c++硬币面值组合枚举法介绍及代码实现
要使用枚举法解决硬币面值组合问题，可以按照以下步骤进行：
1. 定义变量和常量
假设硬币面值分别为1、5、10、25分，用常量COINS表示硬币面值的个
数。
2. 定义组合数和当前组合的变量
定义一个数组current_coin，用于记录当前组合的硬币面值。
3. 遍历所有硬币面值的组合情况
使用两层循环，外层循环控制当前组合的硬币面值的个数，内层循环枚举当
前组合的硬币面值。
4. 判断当前组合的总面值是否符合要求
如果当前组合的总面值等于目标金额，则输出当前组合的硬币面值；否则继
续枚举下一个组合。
下面是C++代码实现：
#include
using namespace std;
const int COINS = 4;
// 硬币面值的个数
const int TARGET = 100;
// 目标金额
int coins[COINS] = {1, 5, 10, 25};
// 硬币面值数组
int current_coin[COINS];
// 当前组合的硬币面值数组
bool used[COINS];
// 记录硬币是否已经被使用过
void dfs(int index) {
// 枚举所有硬币面值的组合情况
if (index == COINS) {
// 当前组合的硬币面值个数已经达到COINS个
int sum = 0;
for (int i = 0; i < COINS; i++) {
// 计算当前组合的总面值
sum += current_coin[i];
if (sum > TARGET) {
// 如果总面值已经超过目标金额，则退出循环
return;
}
}
if (sum == TARGET) {
// 如果总面值等于目标金额，则输出当前组合的硬币
面值
cout << "组合方案：" << endl;
for (int i = 0; i < COINS; i++) {
cout << coins[i] << " ";
}
cout << endl;
}
return;
} else {
// 枚举当前组合的硬币面值，分别为0、1、2、3个硬币面值的情况
for (int i = 0; i <= 3; i++) {
// i表示硬币面值的个数，取值为0~3，
对应4个硬币面值的情况
if (!used[i]) {
// 如果该硬币还没有被使用过，则加入当前组合中
current_coin[index] = coins[i];
used[i] = true;
// 标记该硬币已经被使用过
dfs(index + 1);
// 继续枚举下一个硬币的情况
used[i] = false;
// 回溯，将该硬币标记为未使用过，以便下一次
使用该硬币时可以重新使用它
}
}
}
}
int main() {
// 主函数，调用dfs函数开始枚举所有硬币面值的组合情况
dfs(0);
// 从第一个硬币开始枚举所有组合情况，初始时当前组合的硬币面值个数为
0个
return 0;
}
发布评论