C语言动态规划法解决最大硬币总和问题：逐行代码解释

使用 C 语言动态规划法解决最大硬币总和问题：逐行代码解释

**问题描述：**现有 n 个硬币按顺序依次排列在你面前，它们的面值可以看作一个数组 coins[] = {5, 1, 2, 10, 6, 2}，请在此中选取若干个硬币，使得所取硬币面值总和最大，捡取个数不限，但相邻的硬币不能捡取。请设计动态规划算法，要求能够输出累加值和选取的硬币序号（硬币面值为正数）。

**a. 问题分析：**给定一个硬币数组，要求选取若干个硬币，使得所取硬币面值总和最大，但相邻的硬币不能被选取。

**b. 解题思路：**使用动态规划思想，创建一个大小为 n+1 的数组 dp，dp[i] 表示前 i 个硬币能取得的最大面值总和。递推公式为：dp[i] = max(dp[i-1], dp[i-2]+coins[i-1])，其中 dp[i-1] 表示不选取第 i 个硬币，dp[i-2]+coins[i-1] 表示选取第 i 个硬币。最终返回 dp[n] 即为所求。

c. 代码实现如下：

#include <stdio.h>

int maxCoinValue(int coins[], int n, int *coinIndex) {
    int dp[n+1]; // 创建一个大小为 n+1 的数组 dp
    dp[0] = 0; // 初始化 dp[0] 为 0
    dp[1] = coins[0]; // 初始化 dp[1] 为第一个硬币的面值

    // 逐个计算 dp[i]
    for (int i = 2; i <= n; i++) {
        // 不选取第 i 个硬币，dp[i] 等于前一个硬币的面值总和
        int value1 = dp[i-1];
        // 选取第 i 个硬币，dp[i] 等于前两个硬币的面值总和加上第 i 个硬币的面值
        int value2 = dp[i-2] + coins[i-1];
        // 取两者中的最大值
        dp[i] = (value1 > value2) ? value1 : value2;
    }

    // 回溯选取的硬币
    *coinIndex = n; // 从最后一个硬币开始回溯
    int sum = dp[n]; // 最大面值总和
    while (*coinIndex >= 1) {
        // 如果选取了第 *coinIndex 个硬币，则继续回溯到第 *coinIndex-2 个硬币
        if (dp[*coinIndex] == dp[*coinIndex-2] + coins[*coinIndex-1]) {
            *coinIndex -= 2;
        }
        // 否则继续回溯到第 *coinIndex-1 个硬币
        else {
            *coinIndex -= 1;
        }
    }

    return sum; // 返回最大面值总和
}

int main() {
    int coins[] = {5, 1, 2, 10, 6, 2};
    int n = sizeof(coins) / sizeof(coins[0]);
    int coinIndex = 0;
    int sum = maxCoinValue(coins, n, &coinIndex);

    printf("最大面值总和为：%d\n", sum);
    printf("选取的硬币序号为：");
    for (int i = coinIndex; i < n; i++) {
        printf("%d ", i+1);
    }
    printf("\n");

    return 0;
}

代码注释中解释了每一行代码的作用，包括动态规划的递推公式和回溯选取的硬币。最终输出最大面值总和和选取的硬币序号。