题解 | 购物单

package main

import (
    "fmt"
)

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

func main() {
    var n, m int
    fmt.Scan(&n, &m)
    var value = make([][]int, m+1) // 附件的主件索引是从1开始的
    var weight = make([][]int, m+1)
    var dp = make([]int, n+1)
    var v, w, q int
    for i:=0;i<=m;i++{
        value[i] = make([]int, 3)
        weight[i] = make([]int, 3)
    }
    for i:=1;i<=m;i++{
        fmt.Scan(&v, &w, &q)
        if q == 0{ // 主件
            value[i][0]=v
            weight[i][0]=w*v
        }else if value[q][1] == 0 { // 作为附件1
            value[q][1] =v
            weight[q][1] = w*v
        }else{ // 作为附件2
            value[q][2] =v
            weight[q][2] = w*v
        }
    }

    for i:=1;i<=m;i++{
        for j:= n;j>=0;j-=10{
            if value[i][0]!=0 && value[i][0] <= j { 
                // 只考虑主件
                dp[j] = Max(dp[j], weight[i][0] +  dp[j-value[i][0]])
            }
            if value[i][0]!=0 && value[i][1]!=0 && value[i][0] + value[i][1] <= j{
                // 考虑主件和附件1
                dp[j] = Max(dp[j], weight[i][0] + weight[i][1] + dp[j-value[i][0] - value[i][1]])
            }
            if value[i][0]!=0 && value[i][2]!=0 && value[i][0] + value[i][2] <= j{
                // 考虑主件和附件2
                dp[j] = Max(dp[j], weight[i][0] + weight[i][2] + dp[j-value[i][0] - value[i][2]])
            }
            if value[i][0]!=0 && value[i][1]!=0 && value[i][2]!=0 && value[i][0] + value[i][1] + value[i][2] <= j{
                // 考虑主件、附件1和附件2
                dp[j] = Max(dp[j], weight[i][0] + weight[i][1] + weight[i][2] + dp[j-value[i][0] - value[i][1] - value[i][2]])
            }
        } 
    }
    fmt.Println(dp[n])
}