编辑代码

#include <stdio.h>
#include <stdlib.h>

// 定义最大硬币数量和最大步数
#define MAX_COINS 100
#define MAX_STEPS 100

int max(int a, int b) {
    return (a > b) ? a : b;
}

// 动态规划函数，返回最多可以收集的硬币数量
int collectCoins(int coins[], int n, int steps, int dp[][MAX_STEPS+1], int path[][MAX_STEPS+1]) {
    // 初始化第一行和第一列
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
        path[i][0] = 0;
    }
    for (int j = 0; j <= steps; j++) {
        dp[0][j] = 0;
        path[0][j] = 0;
    }

    // 填充动态规划表
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= steps; j++) {
            if (coins[i-1] <= j) {
                dp[i][j] = max(coins[i-1] + dp[i-1][j-coins[i-1]], dp[i-1][j]);
                if (coins[i-1] + dp[i-1][j-coins[i-1]] > dp[i-1][j]) {
                    path[i][j] = 1;
                } else {
                    path[i][j] = 0;
                }
            } else {
                dp[i][j] = dp[i-1][j];
                path[i][j] = 0;
            }
        }
    }

    // 存储最优解
    int maxCoins = dp[n][steps];
    int selectedCoins[MAX_COINS];
    int count = 0;
    int i = n, j = steps;
    while (i > 0 && j > 0) {
        if (path[i][j] == 1) {
            selectedCoins[count++] = coins[i-1];
            j -= coins[i-1];
            i--;
        } else {
            i--;
        }
    }

    // 打印最优解
    printf("最多可以收集的硬币数量为：%d\n", maxCoins);
    printf("最优解为：");
    for (int k = count - 1; k >= 0; k--) {
        printf("%d ", selectedCoins[k]);
    }
    printf("\n");

    return maxCoins;
}

int main() {
    int coins[] = {5, 1, 2, 10, 6}; // 硬币面值数组
    int n = sizeof(coins) / sizeof(coins[0]); // 硬币个数

    int steps = 12; // 最大步数

    // 定义动态规划表和路径表
    int dp[MAX_COINS+1][MAX_STEPS+1];
    int path[MAX_COINS+1][MAX_STEPS+1];

    int maxCoins = collectCoins(coins, n, steps, dp, path);

    return 0;
}