2024-03-20：用go语言，自 01背包问世之后，小 A 对此深感兴趣。 一天，小 A 去远游，却发现他的背包不同于 01
2024-03-20：用go语言，自 01背包问世之后，小 A 对此深感兴趣。
一天，小 A 去远游，却发现他的背包不同于 01 背包，他的物品大致可分为 k 组。
每组中的物品只能选择1件，现在他想知道最大的利用价值是多少？
答案2024-03-20：
来自左程云。
灵捷3.5
大体步骤如下：
1.定义常量 MAXN 和 MAXM，分别表示物品数量和背包容量的最大值。
2.声明一个二维数组 arr 用于存储物品的重量、价值和组别信息。
3.声明一个一维数组 dp 用于记录每个容量下的最大利用价值。
4.获取输入信息，包括背包容量 m 和物品数量 n。
5.遍历n次，将物品的重量、价值和组别信息存入二维数组 arr。
6.根据物品的组别信息对二维数组 arr 进行排序。
7.初始化数组 dp，将所有元素设置为0。
8.使用动态规划算法计算最大利用价值。遍历每个组别的物品，对于每个容量 r，遍历当前组别的物品，如果容量 r 大于等于物品的重量，则更新 dp[r] 为当前物品的价值加上 dp[r-物品重量] 的最大值。
9.返回 dp[m]，即背包容量为 m 时的最大利用价值。
10.打印结果。
总的时间复杂度是 O(nmlog(n))，其中 n 是物品数量，m 是背包容量。这是因为需要对二维数组 arr 进行排序，排序的时间复杂度是 O(nlog(n))，而计算最大利用价值的动态规划算法的时间复杂度是 O(nm)。
总的额外空间复杂度是 O(n)，其中 n 是物品数量。这是因为需要使用数组 dp 来记录每个容量下的最大利用价值。
go完整代码如下：
package?main
import?(
"fmt"
"sort"
)
const?MAXN?=?1001
const?MAXM?=?1001
var?arr?=?[MAXN][3]int{}
var?dp?=?[MAXM]int{}
var?m,?n?int
func?compute()?int?{
for?start,?end?:=?0,?1;?start?<?n;?{
for?end?<?n?&&?arr[end][2]?==?arr[start][2]?{
end++
}
for?r?:=?m;?r?>=?0;?r--?{
for?i?:=?start;?i?<?end;?i++?{
if?r?>=?arr[i][0]?{
dp[r]?=?max(dp[r],?arr[i][1]+dp[r-arr[i][0]])
}
}
}
start?=?end
end++
}
return?dp[m]
}
func?max(a,?b?int)?int?{
if?a?>?b?{
return?a
}
return?b
}
func?main()?{
inputs?:=?[]int{45,?3,
10,?10,?1,
10,?5,?1,
50,?400,?2}
ii?:=?0
m?=?inputs[ii]
ii++
n?=?inputs[ii]
ii++
for?i?:=?0;?i?<?n;?i++?{
arr[i][0]?=?inputs[ii]
ii++
arr[i][1]?=?inputs[ii]
ii++
arr[i][2]?=?inputs[ii]
ii++
}
sort.Slice(arr[:n],?func(i,?j?int)?bool?{
return?arr[i][2]?<?arr[j][2]
})
for?i?:=?0;?i?<=?m;?i++?{
dp[i]?=?0
}
fmt.Println(compute())
}
在这里插入图片描述python完整代码如下：
#?-*-coding:utf-8-*-
MAXN?=?1001
MAXM?=?1001
arr?=?[[0]?*?3?for?_?in?range(MAXN)]
dp?=?[0]?*?MAXM
m,?n?=?0,?0
def?compute():
start?=?0
while?start?<?n:
end?=?start?+?1
while?end?<?n?and?arr[end][2]?==?arr[start][2]:
end?+=?1
for?r?in?range(m,?-1,?-1):
for?i?in?range(start,?end):
if?r?>=?arr[i][0]:
dp[r]?=?max(dp[r],?arr[i][1]?+?dp[r?-?arr[i][0]])
start?=?end
return?dp[m]
def?max(a,?b):
return?a?if?a?>?b?else?b
inputs?=?[45,?3,
10,?10,?1,
10,?5,?1,
50,?400,?2]
ii?=?0
m?=?inputs[ii]
ii?+=?1
n?=?inputs[ii]
ii?+=?1
for?i?in?range(n):
arr[i][0]?=?inputs[ii]
ii?+=?1
arr[i][1]?=?inputs[ii]
ii?+=?1
arr[i][2]?=?inputs[ii]
ii?+=?1
arr?=?arr[:n]
arr.sort(key=lambda?x:?x[2])
for?i?in?range(m?+?1):
dp[i]?=?0
print(compute())
在这里插入图片描述
- 发表于:
- 原文链接：https://page.om.qq.com/page/OVnD6c1RxIXevzNf4CDYiUYA0
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
