题解 | #购物单#

package main

import "fmt"

func main() {
	//处理数据
	//获取数据
	var total_money, total_count int
	fmt.Scan(&total_money, &total_count)
	primary := make(map[int][]int)
	annex := make(map[int][][]int)
	for i := 0; i < total_count; i++ {
		var money, statisf, annexflag int
		fmt.Scan(&money, &statisf, &annexflag)
		//如果是主键,加入primary字典
		if annexflag == 0 {
			primary[i] = []int{money, statisf}
		} else {
			annex[annexflag-1] = append(annex[annexflag-1], []int{money, statisf})
		}
	}
	//     fmt.Printf("%#v",primary)
	//     fmt.Printf("%#v",annex)
	//计算数据对应的w[i] , v[i]
	sum_money := make([][]int, 0)
	sum_satisf := make([][]int, 0)
	total_count = len(primary)
	for k, v := range primary {
		sum_money = append(sum_money, []int{v[0]}) //主件
		sum_satisf = append(sum_satisf, []int{v[0] * v[1]})
		if annex[k] != nil {
			n := len(annex[k])
			i := len(sum_money)
			if n == 1 { //主件+附件
				sum_money[i-1] = append(sum_money[i-1], v[0]+annex[k][0][0])
				sum_satisf[i-1] = append(sum_satisf[i-1], v[0]*v[1]+annex[k][0][0]*annex[k][0][1])
			} else if n == 2 { //主件+附件1，主件+附件2，主件+附件1+附件2
				sum_money[i-1] = append(sum_money[i-1], v[0]+annex[k][0][0])
				sum_satisf[i-1] = append(sum_satisf[i-1], v[0]*v[1]+annex[k][0][0]*annex[k][0][1])
				sum_money[i-1] = append(sum_money[i-1], v[0]+annex[k][1][0])
				sum_satisf[i-1] = append(sum_satisf[i-1], v[0]*v[1]+annex[k][1][0]*annex[k][1][1])
				sum_money[i-1] = append(sum_money[i-1], v[0]+annex[k][0][0]+annex[k][1][0])
				sum_satisf[i-1] = append(sum_satisf[i-1], v[0]*v[1]+annex[k][0][0]*annex[k][0][1]+annex[k][1][0]*annex[k][1][1])
			}
		}
	}
// 	    fmt.Println(sum_money)
// 	    fmt.Println(sum_satisf)
	//动态 规划
	dp := make([][]int, total_count+1) //代表满意度
	for i := 0; i < total_count+1; i++ {
		dp[i] = make([]int, total_money/10+1)
		// 		dp[i][0] = 0
	}
	// 	for i := 0; i <= total_money/10; i++ {
	// 		dp[0][i] = 0
	// 	}
	for i := 1; i <= total_count; i++ {
		for j := 1; j <= total_money/10; j++ {
			max := dp[i-1][j]
			for k := 0; k < len(sum_money[i-1]); k = k + 1 {
				if j-sum_money[i-1][k]/10 >= 0 {
					if max < dp[i-1][j-sum_money[i-1][k]/10]+sum_satisf[i-1][k] {
						max = dp[i-1][j-sum_money[i-1][k]/10] + sum_satisf[i-1][k]
					}
				}
			}
			dp[i][j] = max
		}
	}
	fmt.Println(dp[total_count][total_money/10])
}