题解 | 购物单

package main

import (
	"fmt"
)

type item struct {
	id         int
	price      int
	importance int
	parentId   int
	value      int
}

type goods struct {
	master      item
	attachments []item
}

// // 得到动态规划，01背包问题的  列数据
func getGoodsGroup(itemNumber int) map[int]goods {
	goodsMap := make(map[int]goods)
	for i := 0; i < itemNumber; i++ {
		good := item{}
		good.id = i + 1
		fmt.Scan(&good.price, &good.importance, &good.parentId)
		good.value = good.price * good.importance
		if good.parentId == 0 {
			// 这是个主件商品
			goods, _ := goodsMap[good.id]
			master := item{
				id:         good.id,
				price:      good.price,
				importance: good.importance,
				parentId:   good.parentId,
				value:      good.price * good.importance,
			}
			goods.master = master
			goodsMap[good.id] = goods
		} else {
			// 这是个附件商品
			parentGoods, _ := goodsMap[good.parentId]
			// 所属主件存在
			parentGoods.attachments = append(parentGoods.attachments, item{
				id:         good.id,
				price:      good.price,
				importance: good.importance,
				parentId:   good.parentId,
				value:      good.price * good.importance,
			})
			goodsMap[good.parentId] = parentGoods

		}
	}
	return goodsMap
}

func main() {
	var totalPrice, itemNumber int
	fmt.Scan(&totalPrice, &itemNumber)
	// 得到动态规划，01背包问题的  列数据
	goodsMap := getGoodsGroup(itemNumber)

	dp := make([]int, totalPrice+1)
	for _, goods := range goodsMap {
		tempDp := make([]int, totalPrice+1)
		copy(tempDp, dp) // 做一个临时变量，防止上一个物品最优解的dp，被污染。
		for j := 1; j <= totalPrice; j++ {
			// 核心原理是：当前选择的满意度 + (背包-当前选择的价格)的满意度 与上一个物品的最优结果做对比
			// 所以(背包-当前选择的价格)的满意度不能收到污染，等本轮j循环完了，再修改上一个物品的最优解
			attachments := 0
			// 只买主件
			if j-goods.master.price >= 0 {
				attachments = goods.master.value + dp[j-goods.master.price]
				tempDp[j] = max(tempDp[j], attachments)
			}

			// 买主件和一个附件
			if len(goods.attachments) > 0 {
				if j-goods.master.price-goods.attachments[0].price >= 0 {
					attachments = goods.master.value + goods.attachments[0].value + dp[j-goods.master.price-goods.attachments[0].price]
					tempDp[j] = max(tempDp[j], attachments)
				}
			}

			if len(goods.attachments) > 1 {
				// 买主件和另一个附件
				if j-goods.master.price-goods.attachments[1].price >= 0 {
					attachments = goods.master.value + goods.attachments[1].value + dp[j-goods.master.price-goods.attachments[1].price]
					tempDp[j] = max(tempDp[j], attachments)
				}

				// 买主件和两个附件
				if j-goods.master.price-goods.attachments[0].price-goods.attachments[1].price >= 0 {
					attachments = goods.master.value + goods.attachments[0].value + goods.attachments[1].value + dp[j-goods.master.price-goods.attachments[0].price-goods.attachments[1].price]
					tempDp[j] = max(tempDp[j], attachments)
				}
			}
		}
		dp = tempDp
		// fmt.Println(masterId, dp)
	}

	fmt.Println(dp[totalPrice])
}

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