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 = 1001const 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 = 1001MAXM = 1001
arr = [[0] * 3 for _ in range(MAXN)]dp = [0] * MAXMm, 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())
复制代码
评论