2022-04-18：things是一个N*3的二维数组，商品有N件，商品编号从1~N，比如things[3] = [300, 2, 6]，代表第3号商品：

原创

福大大架构师每日一题

发布于 2022-04-18 12:56:23

3000

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2022-04-18：things是一个N*3的二维数组，商品有N件，商品编号从1~N，

比如things3 = 300, 2, 6，

代表第3号商品：价格300，重要度2，它是6号商品的附属商品，

再比如things6 = 500, 3, 0，

代表第6号商品：价格500，重要度3，它不是任何附属，它是主商品，

每件商品的收益是价格*重要度，花费就是价格，

如果一个商品是附属品，那么只有它附属的主商品购买了，它才能被购买，

任何一个附属商品，只会有1个主商品，

任何一个主商品的附属商品数量，不会超过2件，

主商品和附属商品的层级最多有2层。

给定二维数组things、钱数money，返回整体花费不超过money的情况下，最大的收益总和。

答案2022-04-18：

本来想用rust写的，但老是编译不通过，实在没辙。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
	money := 1000
	size := 5
	things := [][][]int{{{800, 2, 0}}, {{400, 5, 1}}, {{300, 5, 1}}, {{400, 3, 0}}, {{500, 2, 0}}}
	n := clean(things, size)
	fmt.Println(n)
	ans := maxScore(things, n, money)
	fmt.Println(ans)
}

func clean(things [][][]int, size int) int {
	for i := 0; i < size; i++ {
		cur := things[i][0]
		if cur[2] != 0 {
			things[i] = make([][]int, 0)
			things[cur[2]] = append(things[cur[2]], cur)
		}
	}
	n := 0
	for i := 0; i < size; i++ {
		if len(things[i]) > 0 {
			things[n] = things[i]
			n++
		}
	}
	return n
}

func maxScore(things [][][]int, n, money int) int {
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, money+1)
	}
	for i := 0; i < n; i++ {
		for j := 0; j <= money; j++ {
			dp[i][j] = -2
		}
	}
	return process(things, n, 0, money, dp)
}

func process(things [][][]int, n, index, rest int, dp [][]int) int {
	if rest < 0 {
		return -1
	}
	if index == n {
		return 0
	}
	if dp[index][rest] != -2 {
		return dp[index][rest]
	}
	project := things[index]
	a := project[0]
	var b []int
	if len(project) > 1 {
		b = project[1]
	}
	var c []int
	if len(project) > 2 {
		c = project[2]
	}
	p1 := process(things, n, index+1, rest, dp)
	p2 := process(things, n, index+1, rest-a[0], dp)
	if p2 != -1 {
		p2 += a[0] * a[1]
	}
	p3 := -1
	if b != nil {
		p3 = process(things, n, index+1, rest-a[0]-b[0], dp)
	}
	if p3 != -1 {
		p3 += a[0]*a[1] + b[0]*b[1]
	}
	p4 := -1
	if c != nil {
		p4 = process(things, n, index+1, rest-a[0]-c[0], dp)
	}
	if p4 != -1 {
		p4 += a[0]*a[1] + c[0]*c[1]
	}
	p5 := -1
	if c != nil {
		p5 = process(things, n, index+1, rest-a[0]-b[0]-c[0], dp)
	}
	if p5 != -1 {
		p5 += a[0]*a[1] + b[0]*b[1] + c[0]*c[1]
	}
	ans := getMax(getMax(getMax(p1, p2), getMax(p3, p4)), p5)
	dp[index][rest] = ans
	return ans
}

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