请用c++代码解决这个问题
时间: 2024-10-21 08:04:45 浏览: 9
活动安排问题 贪心法——C++代码
在C++中,可以使用动态规划(Dynamic Programming)的思路来解决零钱兑换的问题。下面是一个简单的C++代码示例:
```cpp
#include <iostream>
#include <vector>
int coinChange(int coins[], int n, int target) {
std::vector<int> dp(target + 1, 0); // 初始化dp数组
dp[0] = 1; // 可以凑出0元的唯一方案是空
for (int i = 1; i <= target; ++i) { // 遍历目标金额
for (int j = 0; j < n; ++j) { // 遍历所有面额
if (coins[j] <= i && dp[i-coins[j]]) { // 如果有足够的硬币且可以组成目标金额
dp[i] = 1; // 更新dp[i]为1(有解)
break;
}
}
}
return dp[target] ? dp[target] : -1; // 返回是否有解,无解返回-1
}
int main() {
int coins[] = {1, 2, 5, 10, 20, 50, 100};
int n = sizeof(coins) / sizeof(coins[0]);
int target = 7;
std::cout << "Number of ways to make change with given coins is: " << coinChange(coins, n, target) << std::endl;
return 0;
}
```
在这个代码中,`coinChange`函数接收面额数组、面额数量以及目标金额作为参数。通过填充dp数组,我们检查是否能找到一种组合,使得可以用给定的面额凑出目标金额。最后返回dp[target],表示是否存在组合方案,若无解则返回-1。
请注意,实际运行此代码需要一个有效的C++环境,并确保面额数组和目标金额已正确设置。
阅读全文