最小硬币问题动态规划C语言
C语言运用动态规划的思想解决最少硬币问题，除了输出最少硬币个数，还输出每种面额的硬币各用了多少个
最少硬币问题是一个经典的动态规划问题，可以使用动态规划思想来解决。下面给出一个 C 语言实现的代码，该代码除了输出最少硬币个数之外，还会输出每种面额的硬币各用了多少个。
#include <stdio.h>
#include <stdlib.h>
void coin_count(int *coins, int n, int target);
int main()
{
// 硬币面额数组
int coins[] = {1, 5, 10, 50};
// 数组长度
int n = sizeof(coins) / sizeof(int);
// 要凑出的金额
int target = 106;
printf("要凑出的金额为：%d\n", target);
coin_count(coins, n, target);
return 0;
}
void coin_count(int *coins, int n, int target)
{
// 动态规划数组，dp[i] 表示凑出金额 i 需要的最少硬币个数
int dp[target + 1];
// used[i] 表示凑出金额 i 使用的最后一枚硬币的面额
int used[target + 1];
// 初始化 dp 数组和 used 数组
for (int i = 0; i <= target; i++)
{
dp[i] = INT_MAX; // 设为一个极大值
used[i] = -1; // 表示没有使用任何硬币
}
dp[0] = 0; // 凑出金额为 0 不需要硬币
// 动态规划转移
for (int i = 1; i <= target; i++)
{
for (int j = 0; j < n; j++)
{
if (i >= coins[j] && dp[i - coins[j]] + 1 < dp[i])
{
dp[i] = dp[i - coins[j]] + 1;
used[i] = coins[j];
}
}
}
// 输出结果
printf("最少需要的硬币个数为：%d\n", dp[target]);
printf("使用的硬币为：");
int count[n];
for (int i = 0; i < n; i++) count[i] = 0;
int k = target;
while (k > 0)
{
int coin = used[k];
count[coin]++;
k -= coin;
}
for (int i = 0; i < n; i++)
{
if (count[coins[i]] > 0)
{
printf("%d元硬币%d枚，", coins[i], count[coins[i]]);
}
}
}
该代码中，动态规划转移的思路非常简单，就是对于每一种面额的硬币，如果能够凑出当前需要凑出的金额且使用这枚硬币后的硬币数比之前更少，则更新 dp 数组和 used 数组。
在输出结果时，我们用一个数组 count 来记录每种面额的硬币使用的数量，然后遍历一遍 count 数组输出每种面额的硬币使用的数量即可。
可参考采纳
#include <stdio.h>
#include <limits.h>
// 定义硬币面额数组和硬币种类数量
int coins[] = {1, 5, 10, 25, 50};
int num_coins = 5;
// 计算最少硬币数量和每种硬币的数量
void countCoins(int amount, int *min_num, int *coin_count) {
int i, j;
int dp[amount+1]; // 动态规划数组
int last_coin[amount+1]; // 记录最后一枚硬币面额
// 初始化动态规划数组和最后一枚硬币面额数组
for (i = 0; i <= amount; i++) {
dp[i] = INT_MAX;
last_coin[i] = -1;
}
dp[0] = 0;
// 动态规划求解最少硬币数量和每种硬币的数量
for (i = 1; i <= amount; i++) {
for (j = 0; j < num_coins; j++) {
if (coins[j] <= i && dp[i-coins[j]]+1 < dp[i]) {
dp[i] = dp[i-coins[j]] + 1;
last_coin[i] = j;
}
}
}
// 输出最少硬币数量
*min_num = dp[amount];
// 统计每种硬币的数量
for (i = 0; i < num_coins; i++) {
coin_count[i] = 0;
}
i = amount;
while (i > 0) {
coin_count[last_coin[i]]++;
i -= coins[last_coin[i]];
}
}
int main() {
int amount, min_num, coin_count[num_coins];
int i;
printf("请输入要找零的金额：");
scanf("%d", &amount);
countCoins(amount, &min_num, coin_count);
printf("最少需要 %d 枚硬币：\n", min_num);
for (i = 0; i < num_coins; i++) {
printf("%d 分硬币 %d 枚\n", coins[i], coin_count[i]);
}
return 0;
}
- 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7738206
- 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：按键菜单程序设计：基于单片机等C语言开发环境的菜单程序设计思路以及代码实现（一）
- 你还可以看下c语言参考手册中的 c语言-求值顺序与定序
- 除此之外, 这篇博客: 这是我看过最全面讲解嵌入式C语言回调函数和函数指针的教程中的 函数指针结构体 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
但是很多时候我们一般在结构体中定义函数指针用的比较多一点。下面再举一个简单的例子。
#include "sys.h" #include "led.h" #include "delay.h" #include "usart.h" /**************************************** * 函数指针结构体 开发者写的结构体 ***************************************/ typedef struct { uint8_t (*p_sum)(uint8_t, uint8_t); uint8_t (*p_sub)(uint8_t, uint8_t); uint8_t (*p_mul)(uint8_t, uint8_t); float (*p_div)(uint8_t, uint8_t); } Operation_T; /*声明结构体变量g_Operation*/ Operation_T g_Operation; /*使用者写的回调函数*/ uint8_t cal_sum(uint8_t a, uint8_t b) { return a + b; } /*使用者写的回调函数*/ uint8_t cal_sub(uint8_t a, uint8_t b) { return a - b; } /*使用者写的回调函数*/ uint8_t cal_mul( uint8_t a, uint8_t b) { return a * b; } /*使用者写的回调函数*/ float cal_div(uint8_t a, uint8_t b) { return a / b; } /*结构体变量g_Operation初始化*/ Operation_T g_Operation = {cal_sum, cal_sub, cal_mul, cal_div}; int main(void) { delay_init(); uart_init(9600); printf("www.zhiguoxin.cn\r\n"); printf("微信公众号：果果小师弟\r\n"); uint8_t a = 10; uint8_t b = 8; /*使用函数指针调用函数*/ printf("%d\r\n", g_Operation.p_sum(a, b)); printf("%d\r\n", g_Operation.p_sub(a, b)); printf("%d\r\n", g_Operation.p_mul(a, b)); printf("%f\r\n", g_Operation.p_div(a, b)); while(1) { } }
- 您还可以看一下 贺利坚老师的C语言及程序设计提高视频精讲课程中的 模块化程序设计及C语言中的函数小节, 巩固相关知识点
如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^
使用动态规划的思想解决最少硬币问题可以按照以下步骤进行：
- 定义问题：最少硬币问题可以描述为：给定一个目标金额amount和一组硬币面额coins，找出组合成目标金额所需的最少硬币个数，并输出每种面额的硬币各使用了多少个。
- 初始化：创建一个大小为amount+1的数组dp，初始值都设置为无穷大（表示无法组成目标金额），dp[0]的初始值为0（表示组成目标金额0不需要硬币）。
- 动态规划转移方程：遍历金额从1到amount，对于每个金额i，依次遍历硬币面额coins[j]，如果当前硬币面额小于等于金额i，并且dp[i - coins[j]] + 1小于dp[i]，则更新dp[i]为dp[i - coins[j]] + 1。
- 追溯最优解：在动态规划转移方程的过程中，记录选择的硬币面额。创建一个大小为amount+1的数组count，初始值都设置为0。在更新dp[i]的同时，如果选择了硬币面额coins[j]，则count[i]等于count[i - coins[j]] + 1。
- 输出结果：最后，输出dp[amount]表示最少硬币个数，以及count数组中每种面额的硬币使用个数。
以下是一个示例的C语言代码实现：
#include <stdio.h>
#include <limits.h>
int minCoins(int coins[], int n, int amount, int count[]) {
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 (coins[j] <= i && dp[i - coins[j]] + 1 < dp[i]) {
dp[i] = dp[i - coins[j]] + 1;
count[i] = count[i - coins[j]] + 1;
}
}
}
return dp[amount];
}
int main() {
int coins[] = {1, 5, 10, 20}; // 硬币面额
int n = sizeof(coins) / sizeof(coins[0]); // 硬币种类数量
int amount = 47; // 目标金额
int count[amount + 1] = {0};
int minCount = minCoins(coins, n, amount, count);
printf("最少硬币个数：%d\n", minCount);
printf("每种面额的硬币使用个数：\n");
for (int i = 1; i <= amount; i++) {
printf("%d元硬币：%d个\n", coins[i - 1], count[i]);
}
return 0;
}
在上述示例代码中，我们通过minCoins函数计算出最少硬币个数，并通过count数组记录每种面额的硬币使用个数。然后在main函数中输出结果。
请注意，以上代码仅为示例，实际使用时可能需要根据具体情况进行适当修改和调整。
以下是C语言的代码实现，用于解决最少硬币问题，并输出每种面额的硬币各使用了多少个。这里使用了动态规划的思想，使用了一个数组来表示所需硬币数量，数组的每个元素表示凑出相应价值所需的最少硬币数量。
#include <stdio.h>
int coin_change(int coins[], int n, int amount) {
int dp[amount + 1];
int used[amount + 1][n];
for (int i = 0; i < amount + 1; i++) {
dp[i] = i;
}
for (int i = 0; i < n; i++) {
for (int j = coins[i]; j <= amount; j++) {
if (dp[j - coins[i]] + 1 < dp[j]) {
dp[j] = dp[j - coins[i]] + 1;
for (int k = 0; k < n; k++) {
if (k == i) {
used[j][k] = used[j - coins[i]][k] + 1;
} else {
used[j][k] = used[j - coins[i]][k];
}
}
}
}
}
printf("Minimum coins needed to make amount %d: %d\n", amount, dp[amount]);
printf("Coins used:\n");
for (int i = 0; i < n; i++) {
printf("%d: %d\n", coins[i], used[amount][i]);
}
}
int main() {
int coins[] = {1, 5, 10, 25};
int n = sizeof(coins) / sizeof(coins[0]);
int amount = 37;
coin_change(coins, n, amount);
return 0;
}
在此示例中，我使用了四个不同的硬币面额，即{1, 5, 10, 25}，并尝试凑出金额37。程序在函数coin_change中执行，最终得到了一个dp数组，其中dp[37] = 4，表示凑出37需要4个硬币。数组used用于记录每种硬币使用的数量，例如used[37][0] = 2，used[37][1] = 1，used[37][2] = 0，used[37][3] = 1，这表示凑出金额37需要使用2枚1美分硬币，1枚5美分硬币，0枚10美分硬币和1枚25美分硬币。
注意：这是一种基于动态规划的背包问题思想的解法，如果硬币种类特别多，可能会导致需要考虑到优化算法等问题，相应的复杂度也会更高。