动态规划最少硬币问题c语言代码

以下是动态规划最少硬币问题的C语言代码（伪代码）：

int coins[] = {1, 5, 10, 25}; // 硬币面额
int n = 4; // 硬币种类数目
int target = 63; // 目标找零金额

int dp[target+1]; // 动态规划数组
dp[0] = 0; // 初始值为0

for (int i = 1; i <= target; i++) {
int minCoins = INT_MAX; // 最小硬币数目
for (int j = 0; j < n; j++) {
if (i >= coins[j]) { // 面额小于等于目标金额时
minCoins = min(minCoins, dp[i-coins[j]] + 1); // 更新最小硬币数目
}
}
dp[i] = minCoins; // 更新动态规划数组
}

printf("最小硬币数目为：%d", dp[target]); // 输出最小硬币数目

相关问题

最少硬币问题，直接给C语言代码

这是一个解决最少硬币问题的C语言代码：

#include <stdio.h>

int countCoins(int coins[], int n, int amount) {
    int dp[amount+1];
    dp[0] = 0;
    
    for (int i = 1; i <= amount; i++) {
        dp[i] = INT_MAX;
        for (int j = 0; j < n; j++) {
            if (i >= coins[j] && dp[i-coins[j]] != INT_MAX && dp[i-coins[j]] + 1 < dp[i]) {
                dp[i] = dp[i-coins[j]] + 1;
            }
        }
    }
    
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    int coins[] = {1, 5, 10, 50};
    int n = sizeof(coins)/sizeof(coins[0]);
    int amount = 62;
    
    int result = countCoins(coins, n, amount);
    printf("Minimum number of coins required: %d", result);
    
    return 0;
}

该代码可以计算在给定数量的硬币中使用最少的硬币来凑出某个金额。

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

其中，第一行输出目标金额；第二行输出凑够目标金额所需的最少硬币数；第三行及之后输出每种面值硬币使用的数量。