编辑代码

#include <stdio.h>

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

// 函数声明
void optimizeTrip(int days, struct Attraction attractions[], int numAttractions);

int main() {
    // 输入景点信息
    struct Attraction attractions[] = {
        {"故宫", 1, 7},
        {"颐和园", 2, 8},
        {"长城", 3, 9},
        {"天坛", 1, 6}
    };

    // 输入旅行天数
    int days = 4;

    // 计算最优景点选择
    optimizeTrip(days, attractions, sizeof(attractions) / sizeof(attractions[0]));

    return 0;
}

// 旅游行程最优化函数
void optimizeTrip(int days, struct Attraction attractions[], int numAttractions) {
    int dp[numAttractions + 1][days + 1];

    for (int i = 0; i <= numAttractions; i++) {
        for (int j = 0; j <= days; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (j >= attractions[i - 1].days)
                dp[i][j] = (dp[i - 1][j] > dp[i - 1][j - attractions[i - 1].days] + attractions[i - 1].score) ?
                            dp[i - 1][j] : (dp[i - 1][j - attractions[i - 1].days] + attractions[i - 1].score);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }

    // 输出最优景点选择
    int i = numAttractions, j = days;
    while (i > 0 && j > 0) {
        if (dp[i][j] != dp[i - 1][j]) {
            printf("选择景点：%s\n", attractions[i - 1].name);
            j -= attractions[i - 1].days;
        }
        i--;
    }
}