题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
package main
import (
"fmt"
)
func main() {
var money, count int
fmt.Scan(&money, &count)
goods := make([][]int, count)
for i := 0; i < count; i++ {
goods[i] = make([]int, 3)
fmt.Scan(&goods[i][0], &goods[i][1], &goods[i][2])
}
costs := make([][]int, 0)
prices := make([][]int, 0)
for i := 0; i < count; i++ {
if goods[i][2] != 0 {
continue
}
cost := make([]int, 0)
price := make([]int, 0)
cost = append(cost, goods[i][0]*goods[i][1])
price = append(price, goods[i][0])
for j := 0; j < count; j++ {
if goods[j][2]-1 == i {
cost = append(cost, goods[j][0]*goods[j][1]+cost[0])
price = append(price, goods[j][0]+price[0])
}
}
if len(cost) == 3 {
cost = append(cost, cost[1]+cost[2]-cost[0])
price = append(price, price[1]+price[2]-price[0])
}
costs = append(costs, cost)
prices = append(prices, price)
}
// size := len(costs)
// dp := make([][]int, size+1)
// for i := 0; i < size+1; i++ {
// dp[i] = make([]int, money+1)
// dp[i][0] = 0
// }
// for j := 0; j < money+1; j += 10 {
// dp[0][j] = 0
// }
// for i := 1; i < size+1; i++ {
// for j := 10; j < money+1; j += 10 {
// max := dp[i-1][j]
// for k, v := range prices[i-1] {
// if j-v >= 0 {
// if max < dp[i-1][j-v]+costs[i-1][k] {
// max = dp[i-1][j-v] + costs[i-1][k]
// }
// }
// }
// dp[i][j] = max
// }
// }
// fmt.Println(dp[size][money])
DpCost(costs, prices, money)
}
func DpCost(cost, price [][]int, money int) {
count := len(price)
packs := make([][]int, count)
for i := 0; i < count; i++ {
temp := make([]int, 0)
for j := 0; j <= money; j++ {
temp = append(temp, -1)
}
packs[i] = temp
}
packs[0][0] = 0
len1 := len(price[0])
for i := 0; i < len1; i++ {
if price[0][i] <= money {
packs[0][price[0][i]] = cost[0][i]
}
}
for i := 1; i < count; i++ {
lastPrice := 0
for j := 0; j <= money; j++ {
if packs[i-1][j] >= 0 {
packs[i][j] = packs[i-1][j]
lastPrice = j
}
}
for j := 0; j <= lastPrice; j++ {
len2 := len(price[i])
for k := 0; k < len2; k++ {
if packs[i-1][j] == -1 {
continue
}
sum := packs[i-1][j] + cost[i][k]
if j+price[i][k] <= money && sum > packs[i][j+price[i][k]] {
packs[i][j+price[i][k]] = sum
}
}
}
}
max := 0
for i := money; i >= 0; i-- {
if packs[count-1][i] > 0 && packs[count-1][i] > max {
max = packs[count-1][i]
}
}
fmt.Println(max)
}
//构造物品
//构造主物品
//由于每个东西只能买一件，并且买了主件才能买附件，同时主键的附件数量是确定的不大于2
//因此我们可以看成购买就是针对于主件，只不过主件的附件数量不同而已，因为只能买一次
//因此主件和附件的搭配只能选一种，之后就可以看成01背包问题，只不过背包的物品是多选一的
//附件直接跳过
//构造各个选择的价格和满意度
//只有主件
//主件加附件1
//主件加附件2
//主件加两个附件
错误示例：
根据题目描述，这是一个经典的背包问题。可以使用动态规划来解决。
首先，创建一个二维数组dp，其中dp[i][j]表示在前i个物品中花费不超过j元的情况下可以达到的最大满意度。
初始化dp数组为0。
然后，遍历每个物品，对于第i个物品：
- 如果该物品是主件（q=0），则考虑将其放入背包。 对于每个可用的预算金额j，更新dp[i][j] = max(dp[i][j], dp[i-1][j-v]+v*w)，其中v是该物品价格，w是该物品重要度。
- 如果该物品是附件（q>0），则需要找到它所属的主件，并判断该主件是否已经放入背包。 如果该主件已经放入背包，则可以考虑将该附件放入背包。 对于每个可用的预算金额j，更新dp[i][j] = max(dp[i][j], dp[i-1][j-v]+v*w)，其中v是该物品价格，w是该物品重要度。如果该主件未放入背包，则不考虑将该附件放入背包。
最后，dp[m][N]即为所求的最大满意度。
以下是Golang的实现：
package main
import (
"fmt"
)
func main() {
var N, m int
fmt.Scan(&N, &m)
items := make([][3]int, m+1)
dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, N+1)
}
for i := 1; i <= m; i++ {
fmt.Scan(&items[i][0], &items[i][1], &items[i][2])
}
for i := 1; i <= m; i++ {
v, w, q := items[i][0], items[i][1], items[i][2]
if q == 0 {
// 主件
for j := N; j >= v; j-- {
dp[i][j] = max(dp[i][j], dp[i-1][j-v]+v*w)
}
} else {
// 附件
if dp[q][N] > 0 {
// 所属主件已经放入背包
for j := N; j >= v; j-- {
dp[i][j] = max(dp[i][j], dp[i-1][j-v]+v*w)
}
}
}
// 将当前物品的满意度传递给下一个物品
for j := 0; j <= N; j++ {
dp[i][j] = max(dp[i][j], dp[i-1][j])
}
}
fmt.Println(dp[m][N])
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
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)
price := make([]int, m+1)
importance := make([]int, m+1)
host := make([]int, m+1)
dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, N/10+1)
}
count := 1
for i := 1; i <= m; i++ {
var v, p, q int
fmt.Scan(&v, &p, &q)
v /= 10 // 将价格除以10，使得价格为整数倍
if q == 0 {
price[count] = v
importance[count] = v * p
host[count] = 0
count++
} else {
if host[q] == 0 {
price[count] = price[q] + v
importance[count] = importance[q] + v*p
host[count] = q
count++
} else if host[q] != 0 && price[host[q]]+v < price[q]+v {
price[count] = price[q] + v
importance[count] = importance[q] + v*p
host[count] = q
count++
}
}
}
for i := 1; i < count; i++ {
for j := N / 10; j >= price[i]; j-- {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-price[i]]+importance[i])
}
}
fmt.Println(dp[count-1][N/10] * 10) // 将满意度乘以10，恢复原始价格
}
根据你的描述，我们可以将购买物品的过程看作一个01背包问题，并进行动态规划求解。以下是一种可能的实现方法：
假设有n个主件可供选择，每个主件分别编号为1到n，对应的价格和满意度分别为price[i]和satisfaction[i]。另外，每个主件可以搭配附件，附件的价格和满意度分别为attachmentPrice[i][j]和attachmentSatisfaction[i][j]，其中i表示主件编号，j表示附件的类型（1或2）。
我们可以定义一个二维数组dp，其中dp[i][j]表示在购买前i个主件时，花费不超过j的情况下的最大满意度。
初始化dp数组为0，然后进行状态转移计算：
for i from 1 to n:for j from budget to price[i]:dp[i][j] = max(dp[i-1][j], dp[i-1][j-price[i]] + satisfaction[i])for j from price[i] to budget:dp[i][j] = max(dp[i][j], dp[i-1][j-price[i]] + satisfaction[i])for k from 1 to 2:for j from attachmentPrice[i][k] to budget:dp[i][j] = max(dp[i][j], dp[i-1][j-attachmentPrice[i][k]] + satisfaction[i] + attachmentSatisfaction[i][k])
最终，dp[n][budget]即为购买主件和附件的最大满意度。
需要注意的是，以上代码中的budget表示可用的总预算，price数组长度为n+1，attachmentPrice和attachmentSatisfaction数组的大小都为(n+1)×3（其中第一列不使用）。
package main
import (
"fmt"
)
func main() {
var N, m int
fmt.Scan(&N, &m)
price := make([]int, m+1)
value := make([]int, m+1)
isAccessory := make([]int, m+1)
mainItem := make([]int, m+1)
dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, N+1)
}
for i := 1; i <= m; i++ {
fmt.Scan(&price[i], &value[i], &isAccessory[i])
mainItem[i] = isAccessory[i]
if isAccessory[i] > 0 {
mainItem[isAccessory[i]] = 0
}
}
for i := 1; i <= m; i++ {
for j := N; j >= 0; j-- {
if isAccessory[i] > 0 {
if j >= price[i]+price[isAccessory[i]] {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-price[i]-price[isAccessory[i]]]+price[i]*value[i]+price[isAccessory[i]]*value[isAccessory[i]])
}
} else {
if j >= price[i] {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-price[i]]+price[i]*value[i])
}
}
}
}
fmt.Println(dp[m][N])
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
以下是使用Go语言实现的代码：
package main
import ("fmt")
func knapsack(N int, m int, items [][]int) int {
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, N+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= N; j++ {
if items[i][0] > j {
dp[i][j] = dp[i-1][j]
} else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-items[i][0]]+items[i][0]*items[i][1])
}
}
}
return dp[m][N]
}
func max(a, b int) int {if a > b {return a}return b}
func main() {var N, m intfmt.Scan(&N, &m)
items := make([][]int, m+1)
items[0] = []int{0, 0}
for i := 1; i <= m; i++ {
var p, w, q int
fmt.Scan(&p, &w, &q)
items[i] = []int{p, p * w}
if q != 0 {
items[q][0] += p
}
}
fmt.Println(knapsack(N, m, items))
}
您可以将输入数据按照指定格式输入，然后运行该程序即可得到结果。希望这个Go语言版本的代码能够帮助到您。如果您还有任何问题，请随时告诉我。
package main
import (
"fmt"
)
func knapsack(N int, m int, items [][]int) int {
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, N+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= N; j++ {
if items[i][0] > j {
dp[i][j] = dp[i-1][j]
} else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-items[i][0]]+items[i][0]*items[i][1])
}
}
}
return dp[m][N]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
var N, m int
fmt.Scan(&N, &m)
items := make([][]int, m+1)
items[0] = []int{0, 0}
for i := 1; i <= m; i++ {
var p, w, q int
fmt.Scan(&p, &w, &q)
items[i] = []int{p, p * w}
if q != 0 {
items[q][0] += p
}
}
fmt.Println(knapsack(N, m, items))
}
这个解决方案使用了一个二维数组dp来保存中间的结果。其中dp[i][j]表示在前i个物品中选择总价值不超过j的物品时，价值与重要度乘积的总和的最大值。对于每个物品i，我们可以选择将其作为主件或附件来计算最大值。如果选择将物品i作为主件，那么我们需要考虑j是否大于等于物品i的价格，如果是，我们就可以选择将物品i作为主件，并在剩余的价值范围内选择其他物品。如果选择将物品i作为附件，那么我们需要找到物品i所属的主件，并在剩余的价值范围内选择其他物品。我们可以通过动态规划的方式逐步计算出最终的结果。最后，我们返回dp[m][N]作为最大值。
描述:王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
主件 附件
电脑 打印机，扫描仪
书柜 图书
书桌 台灯，文具
工作椅 无
如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。
每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。
王强查到了每件物品的价格（都是 10 元的整数倍），而他只有 N 元的预算。除此之外，他给每件物品规定了一个重要度，用整数 1 ~ 5 表示。他希望在花费不超过 N 元的前提下，使自己的满意度达到最大。
满意度是指所购买的每件物品的价格与重要度的乘积的总和，假设设第ii件物品的价格为v[i]，重要度为w[i]，共选中了k件物品，编号依次为j1,j2,...,jk ，则满意度为：v[j1]*w[j1]+v[j2]*w[j2]+ … +v[jk]*w[jk]。（其中 * 为乘号）
请你帮助王强计算可获得的最大的满意度。
输入描述：
输入的第 1 行，为两个正整数N，m，用一个空格隔开：
（其中 N （ N<32000 ）表示总钱数， m （m <60 ）为可购买的物品的个数。）
从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q
（其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）
输出描述：输出一个正整数，为张强可以获得的最大的满意度。
错误：
func main() {
var N, m int
fmt.Scan(&N, &m)
v := make([]int, m+1)
w := make([]int, m+1)
q := make([]int, m+1)
dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, N+1)
}
reader := bufio.NewReader(os.Stdin)
for i := 1; i <= m; i++ {
fmt.Fscan(reader, &v[i], &w[i], &q[i])
v[i] = v[i] / 10
}
for i := 1; i <= m; i++ {
if q[i] == 0 {
// 主件
for j := N; j >= v[i]; j-- {
dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]]+v[i]*w[i])
}
} else {
// 附件
for j := N; j >= v[i]+v[q[i]]; j-- {
dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]]+v[i]*w[i], dp[i-1][j-v[i]-v[q[i]]]+v[i]*w[i]+v[q[i]]*w[q[i]])
}
}
}
fmt.Println(dp[m][N] * 10)
}
func max(nums ...int) int {
maxVal := nums[0]
for _, num := range nums {
if num > maxVal {
maxVal = num
}
}
return maxVal
}
