编辑代码

#include <stdio.h>

#define MAX_DAYS 4
#define NUM_SPOTS 4

// 定义景点的结构体
struct Spot {
    char name[20];
    int days;
    int score;
};

// 动态规划函数
void knapsack(struct Spot spots[], int n) {
    int dp[MAX_DAYS + 1] = {0}; // dp数组，表示不同时间下的最大评分
    int selected[NUM_SPOTS][MAX_DAYS + 1] = {0}; // 记录选取的景点

    for (int i = 0; i < n; ++i) {
        for (int j = MAX_DAYS; j >= spots[i].days; --j) {
            // 在当前时间下选择该景点或者不选择该景点
            if (dp[j] < dp[j - spots[i].days] + spots[i].score) {
                dp[j] = dp[j - spots[i].days] + spots[i].score;
                selected[i][j] = 1; // 标记选取了第i个景点
            }
        }
    }

    // 打印选取的景点
    printf("选取的景点为：");
    int daysLeft = MAX_DAYS;
    for (int i = n - 1; i >= 0; --i) {
        if (selected[i][daysLeft]) {
            printf("%s  ", spots[i].name);
            daysLeft -= spots[i].days;
        }
    }
    printf("\n获得最大价值评分为：%d", dp[MAX_DAYS]);
}

int main() {
    // 初始化景点信息
    struct Spot spots[NUM_SPOTS] = {
        {"故宫", 1, 7},
        {"颐和园", 2, 8},
        {"长城", 3, 9},
        {"天坛", 1, 6}
    };

    // 调用动态规划函数
    knapsack(spots, NUM_SPOTS);

    return 0;
}