2024-03-20：用go语言，自 01背包问世之后，小 A 对此深感兴趣。

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完整代码如下：

packagemain
import(
"fmt"
"sort"
)
constMAXN=1001
constMAXM=1001
vararr=[MAXN][3]int{}
vardp=[MAXM]int{}
varm,nint
funccompute()int{
forstart,end:=0,1;startforendend++
}
forr:=m;r>=0;r--{
fori:=start;iifr>=arr[i][0]{
dp[r]=max(dp[r],arr[i][1]+dp[r-arr[i][0]])
}
}
}
start=end
end++
}
returndp[m]
}
funcmax(a,bint)int{
ifa>b{
returna
}
returnb
}
funcmain(){
inputs:=[]int{45,3,
10,10,1,
10,5,1,
50,400,2}
ii:=0
m=inputs[ii]
ii++
n=inputs[ii]
ii++
fori:=0;iarr[i][0]=inputs[ii]
ii++
arr[i][1]=inputs[ii]
ii++
arr[i][2]=inputs[ii]
ii++
}
sort.Slice(arr[:n],func(i,jint)bool{
returnarr[i][2]})
fori:=0;i<=m;i++{
dp[i]=0
}
fmt.Println(compute())
}

python完整代码如下：

#-*-coding:utf-8-*-
MAXN=1001
MAXM=1001
arr=[[0]*3for_inrange(MAXN)]
dp=[0]*MAXM
m,n=0,0
defcompute():
start=0
whilestartend=start+1
whileendend+=1
forrinrange(m,-1,-1):
foriinrange(start,end):
ifr>=arr[i][0]:
dp[r]=max(dp[r],arr[i][1]+dp[r-arr[i][0]])
start=end
returndp[m]
defmax(a,b):
returnaifa>belseb
inputs=[45,3,
10,10,1,
10,5,1,
50,400,2]
ii=0
m=inputs[ii]
ii+=1
n=inputs[ii]
ii+=1
foriinrange(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=lambdax:x[2])
foriinrange(m+1):
dp[i]=0
print(compute())