穷举法c++的例子,中等难度
时间: 2024-09-11 15:04:42 浏览: 29
穷举法是一种通过遍历所有可能的情况来解决问题的算法思想。在C++中,我们可以通过嵌套循环来实现穷举。下面是一个使用穷举法解决中等难度问题的例子:
问题描述:有一个整数数组,每个元素表示一个硬币的面值,数组中至少包含一个硬币的面值为1。现在我们要计算硬币的组合方式,使得组合出的总金额为一个指定的金额。
例子代码:
```cpp
#include <iostream>
using namespace std;
int countWays(int coins[], int coinsSize, int amount) {
// 创建一个数组来保存每个金额的组合数,初始为0
int dp[amount + 1] = {0};
// 组合出金额0的方式有1种,即什么都不选
dp[0] = 1;
// 遍历所有的硬币面值
for (int i = 0; i < coinsSize; i++) {
// 遍历所有的金额值
for (int j = coins[i]; j <= amount; j++) {
// 通过加上当前硬币面值,得到新的金额
// dp[j-coins[i]]表示在不使用当前硬币的情况下组合金额j-coins[i]的方式数
// dp[j]是加上当前硬币面值后的组合方式数
dp[j] += dp[j - coins[i]];
}
}
// 返回组合出指定金额的方式数
return dp[amount];
}
int main() {
int coins[] = {1, 2, 5}; // 硬币面值数组
int coinsSize = sizeof(coins) / sizeof(coins[0]); // 硬币面值数组的大小
int amount = 5; // 指定的总金额
cout << "Total combinations: " << countWays(coins, coinsSize, amount) << endl;
return 0;
}
```
在这个例子中,我们定义了一个数组 `dp` 来记录每个金额的组合数。我们首先初始化 `dp[0]` 为1,表示金额为0的组合方式有1种(什么都不选)。然后,我们遍历每个硬币,并更新 `dp` 数组的值,最终 `dp[amount]` 就是我们想要的答案。
阅读全文