编辑代码

package main

import (
	"fmt"
)

func optimizeTrip(days int, spots []Spot) {
	n := len(spots)
	dp := make([][]int, n+1)

	for i := range dp {
		dp[i] = make([]int, days+1)
	}

	for i := 1; i <= n; i++ {
		for j := 0; j <= days; j++ {
			dp[i][j] = dp[i-1][j]
			if j >= spots[i-1].Time {
				dp[i][j] = max(dp[i][j], dp[i-1][j-spots[i-1].Time]+spots[i-1].Score)
			}
		}
	}

	// 回溯获取最大价值对应的景点选择路径
	selectedSpots := make([]Spot, 0)
	i, j := n, days
	for i > 0 && j > 0 {
		if dp[i][j] != dp[i-1][j] {
			selectedSpots = append(selectedSpots, spots[i-1])
			j -= spots[i-1].Time
		}
		i--
	}

	// 打印结果
	fmt.Println("选择的景点:")
	for i := len(selectedSpots) - 1; i >= 0; i-- {
		fmt.Printf("%s\t%d天\t%d评分\n", selectedSpots[i].Name, selectedSpots[i].Time, selectedSpots[i].Score)
	}
	fmt.Printf("总评分:%d\n", dp[n][days])
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

type Spot struct {
	Name  string
	Time  int
	Score int
}

func main() {
	days := 4
	spots := []Spot{
		{"故宫", 1, 7},
		{"颐和园", 2, 8},
		{"长城", 3, 9},
		{"天坛", 1, 6},
	}

	optimizeTrip(days, spots)
}