题解 | #购物单#

package main

import (
	"fmt"

)

func main() {
    N,m:= 0,0
    fmt.Scan(&N, &m)

    val := make([][]int, 0)
    wei := make([][]int, 0)
    maj := make([]int, 0)
    satis := make(map[int][]int, 0)
    cost := make(map[int][]int, 0)
    for  {
        v,p,q := 0,0,0
        n, _ := fmt.Scan(&v,&p,&q)
        if n == 0 {
            break
        }

        val = append(val, []int{v}) // 价格
        wei = append(wei, []int{p}) // 重要度
        maj = append(maj, q) // 主件/附件
        if q == 0 {
            satis[len(val)] = []int{v * p}    // 主件满意度
            cost[len(val)] = []int{v}         // 主件价格
        }
        
    }


    // key是主件索引，val是他的几种价值情况
    // 计算有附件时的满意度
    // 对应j=0~3 主件；主件+附件1；主件+附件2；主件+附件1+附件2

    for i, v := range maj {
        if v == 0 {
            // 主件跳过
            continue
        }
    
        // 将附件的三种情况添加到主件的价格和重要度中

        // 将附件加入到主件中，可能是主件+附件1，或者主件+附件2
        // 计算主件满意度+附件1/2满意度
        satis[v] = append(satis[v], satis[v][0] + val[i][0] * wei[i][0])
        cost[v] = append(cost[v], cost[v][0] + val[i][0])

        if len(satis[v]) > 2 { 
            // 说明该主件已经有附件1了，刚刚加的是附件2，还要加上：主件+附件1+附件2
            // satis[v][1] 就是主件+附件1的情况，不需要再加主件
            satis[v] = append(satis[v], satis[v][1] + val[i][0] * wei[i][0])
            cost[v] = append(cost[v], cost[v][1] + val[i][0])
        }
    }

    // fmt.Println("satis",satis)
    // fmt.Println("cost", cost)

    s := make([][]int, 0)
    c := make([][]int, 0)
    for k, v := range satis {
        s = append(s, v)
        c = append(c, cost[k])
    }


    // 更新物品个数为主件数量
    m = len(s)

    // 声明dp, i为物品是否购买，j为总价格
    // dp[i][j] 表示0-i物品最大满意度
    dp := make([][]int, m)
    for i:=0;i<m;i++ {
        dp[i] = make([]int, N+1)
    }


    // 初始化 第一个物品的dp
    for j:=c[0][0];j<=N;j=j+10 {
        for k, v := range c[0] {
            if j >= v { // 钱够时才放进去
                dp[0][j] = s[0][k]
            }
        }
    }


    for i:=1;i<m;i++ {
        for j:=0;j<=N;j=j+10 {
            // 由于是一组物品，所以每个情况都要判断是否金额足够，然后找到满意度最大的。
            max_s := dp[i-1][j] // 不放入第i个时的满意度
            for k, v := range c[i] {
                if j>= v { // 余额足够, 取最大的一种
                    max_s = max(max_s, dp[i-1][j-v]+s[i][k]) // 记得减去消耗的钱
                }
            }
            dp[i][j] = max_s
        }
    }


    fmt.Println(dp[m-1][N])
}

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