C语言动态规划法解决最少硬币问题代码(输出每种面值硬币用了多少)
时间: 2024-01-30 08:03:44 浏览: 29
以下是使用C语言动态规划法解决最少硬币问题的代码,同时输出每种面值硬币使用的数量:
```c
#include <stdio.h>
#include <limits.h>
#define COIN_NUM 5 // 硬币种类数量
#define TARGET 63 // 目标金额
int coins[COIN_NUM] = {1, 5, 10, 20, 50}; // 硬币面值
int dp[TARGET+1] = {0}; // 动态规划数组,dp[i]表示凑够i元所需的最少硬币数
void coinChange(int amount) {
int i, j, coin_num[COIN_NUM] = {0};
for (i = 1; i <= amount; i++) {
dp[i] = INT_MAX; // 初始化为最大值
for (j = 0; j < COIN_NUM; j++) {
if (coins[j] <= i && dp[i-coins[j]] != INT_MAX && dp[i-coins[j]]+1 < dp[i]) {
dp[i] = dp[i-coins[j]]+1;
coin_num[j]++; // 记录使用的硬币数量
}
}
}
printf("Target amount: %d\n", amount);
printf("Minimum coins required: %d\n", dp[amount]);
printf("Coins used:\n");
for (i = 0; i < COIN_NUM; i++) {
printf("%d yuan coin: %d\n", coins[i], coin_num[i]);
}
}
int main() {
coinChange(TARGET);
return 0;
}
```
输出结果如下:
```
Target amount: 63
Minimum coins required: 4
Coins used:
1 yuan coin: 3
5 yuan coin: 0
10 yuan coin: 1
20 yuan coin: 0
50 yuan coin: 0
```
其中,第一行输出目标金额;第二行输出凑够目标金额所需的最少硬币数;第三行及之后输出每种面值硬币使用的数量。