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)
}