题解 | #购物单# Golang实现

package main

import (
	"fmt"
)

type Good struct {
	price      int
	value      int
	relyOn     int
	id         int
	attachment []Good
}

func (c *Good) AddAttachment(good Good) {
	c.attachment = append(c.attachment, good)
}
func (c *Good) CalculateSatisfaction(n int) int {
	switch n {
	case 0:
		return c.price * c.value
	case 1:
		return c.price*c.value + c.attachment[0].price*c.attachment[0].value
	case 2:
		return c.price*c.value + c.attachment[1].price*c.attachment[1].value
	case 3:
		return c.price*c.value + c.attachment[0].price*c.attachment[0].value + c.attachment[1].price*c.attachment[1].value
	}
	return 114514
}

func (c *Good) CalculatePrice(n int) int {
	switch n {
	case 0:
		return c.price
	case 1:
		return c.price + c.attachment[0].price
	case 2:
		return c.price + c.attachment[1].price
	case 3:
		return c.price + c.attachment[0].price + c.attachment[1].price
	}
	return 114514
}

func (c Good) Check(n int) bool {
	if n == 0 {
		return true
	}
	if n == 1 && len(c.attachment) >= 1 {
		return true
	}
	if n > 1 && len(c.attachment) >= 2 {
		return true
	}
	return false
}

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

func main() {
	var N, m int
	var goods []Good
	var attachments []Good
	fmt.Scanf("%d %d", &N, &m)
	for i := 1; i <= m; i++ {
		var price, value, isAttachment int
		fmt.Scanf("%d %d %d", &price, &value, &isAttachment)
		if isAttachment == 0 {
			goods = append(goods, Good{
				price:      price,
				value:      value,
				relyOn:     -1,
				id:         i,
				attachment: []Good{},
			})
		} else {
			attachments = append(attachments, Good{
				price:      price,
				value:      value,
				id:         -1,
				relyOn:     isAttachment,
				attachment: nil})
		}
	}
	for _, v := range attachments {
		idx := 0
		for j, val := range goods {
			if val.id == v.relyOn {
				idx = j
				break
			}
		}
		goods[idx].AddAttachment(v)
	}
	dp := make([][]int, len(goods)+1)
	for i := 0; i <= len(goods); i++ {
		dp[i] = make([]int, N+1)
	}

	for i := 1; i < len(dp); i++ {
		for j := 0; j < len(dp[0]); j += 10 {
			dp[i][j] = dp[i-1][j]
			for k := 0; k <= 3; k++ {
				if !goods[i-1].Check(k) {
					continue
				}
				if j >= goods[i-1].CalculatePrice(k) {
					//fmt.Printf("i:%d j:%d k:%d dpi-1j: %d res:%d\n", i, j, k, dp[i-1][j], dp[i-1][j-goods[i-1].CalculatePrice(k)]+goods[i-1].CalculateSatisfaction(k))
					dp[i][j] = max(dp[i][j], dp[i-1][j-goods[i-1].CalculatePrice(k)]+goods[i-1].CalculateSatisfaction(k))

				}
			}
		}
	}

	fmt.Printf("%d\n", dp[len(goods)][N])

}

Golang实现，欢迎大家一起讨论。