题解 | #购物单#

package main

import (
    "fmt"
)

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

func calculate(N int, m int, prices [][3]int, sat [][3]int) int {
    // ref: https://juejin.cn/post/7090728598772350990
    // prices[i][j]: 表示第 i 件物品的第 j 件副品的价格(0: 无副品，1: 第一件副品，2: 第二件副品)
    // sat[i][j]: 表示第 i 件物品第 j 件副品的满意度

    // dp[i][j]: 表示考虑前 i 个物品，且总钱数为 j 所能获取的最大满意度, dp[m][N] 即为所求
    dp := make([][]int, m+1)
    for i:=0; i<=m; i++ {
        dp[i] = make([]int, N+1)
    }

    // 初始化: 从 1 开始便利，默认初始化为 0

    // 动态转移方程
    for i:=1; i<=m; i++ {
        for j:=1; j<=N; j++ {
            if j < prices[i][0] {
                // 如果钱不够买一个主件
                dp[i][j] = dp[i-1][j]
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-prices[i][0]] + sat[i][0])
            }

            // 如果够买一个主件和第一个附件
            if j >= prices[i][0] + prices[i][1] {
                dp[i][j] = max(dp[i][j], dp[i-1][j-prices[i][0]-prices[i][1]] + sat[i][0] + sat[i][1])
            }
            // 如果够买一个主件和第二个附件
            if j >= prices[i][0] + prices[i][2] {
                dp[i][j] = max(dp[i][j], dp[i-1][j-prices[i][0]-prices[i][2]] + sat[i][0] + sat[i][2])
            }
            // 如果够买一个主件和第一个附件和第二个附件
            if j>= prices[i][0] + prices[i][1] + prices[i][2] {
                dp[i][j] = max(dp[i][j], dp[i-1][j-prices[i][0]-prices[i][1]-prices[i][2]] + sat[i][0] + sat[i][1] + sat[i][2])
            }
        }
    }
    return dp[m][N]
}


func main() {
    var N, m int

    fmt.Scan(&N, &m)

    prices := make([][3]int, m+1)
    sat := make([][3]int, m+1)

    for i:=1; i<=m; i++ {
        var v, p, q int
        fmt.Scan(&v, &p, &q)

        satisfation := v * p
        if q == 0 {
            prices[i][0] = v
            sat[i][0] = satisfation
        } else {
            // 如果是副件
            if (prices[q][1] == 0) {
                // 第一个副件
                prices[q][1] = v
                sat[q][1] = satisfation
            } else {
                // 第二个副件
                prices[q][2] = v
                sat[q][2] = satisfation
            }
        }
    }

    maxSatisfaction := calculate(N, m, prices, sat)
    fmt.Println(maxSatisfaction)
}

// 本题输入多行数字，用空格隔开，所以采用: fmt.Scan(&n) 的方式