题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
参考0-1背包问题，使用golang编写得到的结果。其中dp数组的大小可以进一步优化，但是最主要的是要清楚算法思想，和附属物件的处理方式。该算法使用额外的两个切片遍历了每个主物件可能存在的全部购买方式，并使用dp数组记录每个主物件加入与否的最大收益情况。
package main
import (
"fmt"
)
type Product struct{
v int
p int
q int
ann []Product
}
func main(){
var N,m int
fmt.Scan(&N,&m)
nums:=make([]Product,m)
de:=make([]int,0)
for i:=0;i<m;i++{//读取多行输入
var a,b,c int
fmt.Scan(&a,&b,&c)
//fmt.Println(len(s[2]))
//fmt.Println(a,b,c)
temp:=Product{a/10,b,c,nil}
nums[i]=temp
}
// fmt.Println(nums)
for i:=0;i<len(nums);i++{//处理附属关系
if nums[i].q!=0{
nums[nums[i].q-1].ann=append(nums[nums[i].q-1].ann,nums[i])
de=append(de,i)
}
}
for j,i:= range de {//生成只有主物件存在的切片
nums=append(nums[:i-j],nums[i-j+1:]...)
}
//fmt.Println(nums)
m=len(nums)
w,v:=make([][]int,0),make([][]int,0)//存储每个节点可能存在的组合购买情况
for i:=0;i<m;i++ {//遍历得到主物件的组合购买情况
w_temp,v_temp:=make([]int,0),make([]int,0)
w_temp = append(w_temp, nums[i].v)
v_temp = append(v_temp, nums[i].p*nums[i].v)
for j:=0;j<len(nums[i].ann);j++{
w_temp = append(w_temp, nums[i].v+nums[i].ann[j].v)
v_temp = append(v_temp, nums[i].p*nums[i].v+nums[i].ann[j].v*nums[i].ann[j].p)
if j==1{
w_temp = append(w_temp, nums[i].v+nums[i].ann[0].v+nums[i].ann[1].v)
v_temp = append(v_temp, nums[i].p*nums[i].v+nums[i].ann[0].v*nums[i].ann[0].p+nums[i].ann[1].v*nums[i].ann[1].p)
}
}
w = append(w, w_temp)
v = append(v, v_temp)
}
dp:=make([][]int,m+1)//定义dp数组，i为加入主物件的编号，j为当前所用的金额总数。
for i:=0;i<m+1;i++{
dp[i]=make([]int,N/10+1)
}
for i:=1;i<m+1;i++{//把一个一个主物件加入购买队列，计算最高的利益
for j:=0;j<N/10+1;j=j+1{
max_i:=dp[i-1][j]//在核对购买附属情况前要先用一个中间变量存储当前的最高利益，已确保最终该变量就是对应最高利益。
for k:=0;k<len(w[i-1]);k++{
if j-w[i-1][k]>=0{
max_i=max(max_i,dp[i-1][j-w[i-1][k]]+v[i-1][k])
}
dp[i][j]=max_i
}
}
}
fmt.Printf("%d",dp[m][N/10]*10)
}
func max(a,b int) int {
if a>b{
return a
}else {
return b
}
}
