编辑代码


// 定义最大景点数量和最大旅行天数
#define MAX_SIGHTS 4
#define MAX_DAYS 4

int max(int a, int b) {
    return (a > b) ? a : b;
}
// 打印最优旅行方案
void tour(int sights[MAX_SIGHTS][2], int days) {
    int dp[MAX_SIGHTS + 1][MAX_DAYS + 1];// 定义了一个二维数组dp,用于保存动态规划的结果
    int i, j;

    // 初始化动态规划数组
    for (i = 0; i <= MAX_SIGHTS; i++) {
        for (j = 0; j <= MAX_DAYS; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (sights[i - 1][0] > j)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - sights[i - 1][0]] + sights[i - 1][1]);
        }
    }

    // 打印最优旅行价值和选中的景点
    printf("最优旅行价值:%d\n", dp[MAX_SIGHTS][days]);
    printf("选中的景点:\n");
    
    i = MAX_SIGHTS;
j = days;
//根据动态规划的结果,回溯选中的景点
    while (i > 0 && j > 0) {
        if (dp[i][j] != dp[i - 1][j]) {
            printf("景点%d\n", i);
            j -= sights[i - 1][0];
        }
        i--;
    }
}

int main() {
    int sights[MAX_SIGHTS][2] = {{1, 7}, {2, 8}, {3, 9}, {1, 6}};
    int days = 4;
    
    tour(sights, days);
    
    return 0;
}