2024-03-27：用go语言，多维费用背包。 给你一个二进制字符串数

2024-03-27：用go语言，多维费用背包。

给你一个二进制字符串数组 strs 和两个整数 m 和 n，

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集。

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3。

输出：4。

答案2024-03-27：

来自左程云。

灵捷3.5

大体步骤如下：

1.函数使用递归的方式实现。它遍历字符串数组，将每个字符串中0和1的数量存储在一个二维数组中。然后通过递归函数进行计算，不断比较所选字符串是否符合要求，选择放入或不放入子集。该方法的时间复杂度为O(2^n)，空间复杂度为O(n)。

findMaxForm1

strs

arr

process1

2.函数使用记忆化搜索的方式实现。它也遍历字符串数组得到二维数组，但使用三维数组进行记忆化，记录已经计算过的结果，避免重复计算。该方法的时间复杂度为O(m * n * len(strs))，空间复杂度为O(m * n * len(strs))。

findMaxForm2

strs

arr

dp

3.函数使用动态规划的方式实现。它从后向前遍历字符串数组，得到二维数组来保存计算结果。通过比较选择当前字符串加入子集还是不加入子集，并更新动态规划数组。该方法的时间复杂度为O(m * n * len(strs))，空间复杂度为O(m * n * len(strs))。

findMaxForm3

strs

dp

dp

4函数使用动态规划的方式实现。它遍历字符串数组，得到二维数组来保存计算结果。使用一维数组进行滚动更新，从后向前遍历，根据当前字符串的0和1的数量，更新动态规划数组。该方法的时间复杂度为O(m * n * len(strs))，空间复杂度为O(m * n)。

findMaxForm4

strs

dp

dp

dp

总时间复杂度：O(m * n * len(strs))

总额外空间复杂度：O(m * n * len(strs))

Go完整代码如下：

packagemain
import(
"fmt"
)
varzeros,onesint
funcfindMaxForm1(strs[]string,mint,nint)int{
len:=len(strs)
arr:=make([][]int,len)
fori:=0;izeroAndOne(strs[i])
arr[i]=[]int{zeros,ones}
}
returnprocess1(arr,0,m,n)
}
funcprocess1(arr[][]int,iint,zint,oint)int{
ifi==len(arr){
return0
}
p1:=process1(arr,i+1,z,o)
p2:=0
ifarr[i][0]<=z&&arr[i][1]<=o{
p2=1+process1(arr,i+1,z-arr[i][0],o-arr[i][1])
}
ifp1>p2{
returnp1
}
returnp2
}
funcfindMaxForm2(strs[]string,mint,nint)int{
len:=len(strs)
arr:=make([][]int,len)
fori:=0;izeroAndOne(strs[i])
arr[i]=[]int{zeros,ones}
}
dp:=make([][][]int,len)
fori:=0;idp[i]=make([][]int,m+1)
forj:=0;j<=m;j++{
dp[i][j]=make([]int,n+1)
fork:=0;k<=n;k++{
dp[i][j][k]=-1
}
}
}
returnprocess2(arr,0,m,n,dp)
}
funcprocess2(arr[][]int,iint,zint,oint,dp[][][]int)int{
ifi==len(arr){
return0
}
ifdp[i][z][o]!=-1{
returndp[i][z][o]
}
p1:=process2(arr,i+1,z,o,dp)
p2:=0
ifarr[i][0]<=z&&arr[i][1]<=o{
p2=1+process2(arr,i+1,z-arr[i][0],o-arr[i][1],dp)
}
ans:=p1
ifp2>p1{
ans=p2
}
dp[i][z][o]=ans
returnans
}
funcfindMaxForm3(strs[]string,mint,nint)int{
len0:=len(strs)
dp:=make([][][]int,len0+1)
fori:=len0;i>=0;i--{
dp[i]=make([][]int,m+1)
forz:=0;z<=m;z++{
dp[i][z]=make([]int,n+1)
}
}
fori:=len0-1;i>=0;i--{
zeroAndOne(strs[i])
forz:=0;z<=m;z++{
foro:=0;o<=n;o++{
dp[i][z][o]=dp[i+1][z][o]
ifzeros<=z&&ones<=o{
dp[i][z][o]=max(dp[i][z][o],1+dp[i+1][z-zeros][o-ones])
}
}
}
}
returndp[0][m][n]
}
funczeroAndOne(strstring){
zeros=0
ones=0
fori:=0;iifstr[i]=='0'{
zeros++
}else{
ones++
}
}
}
funcfindMaxForm4(strs[]string,mint,nint)int{
dp:=make([][]int,m+1)
fori:=0;i<=m;i++{
dp[i]=make([]int,n+1)
}
for_,s:=rangestrs{
zeroAndOne(s)
fori:=m;i>=zeros;i--{
forj:=n;j>=ones;j--{
dp[i][j]=max(dp[i][j],dp[i-zeros][j-ones]+1)
}
}
}
returndp[m][n]
}
funcmax(a,bint)int{
ifa>b{
returna
}
returnb
}
funcmain(){
strs:=[]string{"10","0001","111001","1","0"}
m:=5
n:=3
res1:=findMaxForm1(strs,m,n)
fmt.Println("findMaxForm1:",res1)
res2:=findMaxForm2(strs,m,n)
fmt.Println("findMaxForm2:",res2)
res3:=findMaxForm3(strs,m,n)
fmt.Println("findMaxForm3:",res3)
res4:=findMaxForm4(strs,m,n)
fmt.Println("findMaxForm4:",res4)
}

Python完整代码如下：

#-*-coding:utf-8-*-
defzero_and_one(string):
zeros=0
ones=0
forcharinstring:
ifchar=='0':
zeros+=1
else:
ones+=1
returnzeros,ones
deffind_max_form1(strs,m,n):
length=len(strs)
arr=[]
foriinrange(length):
zeros,ones=zero_and_one(strs[i])
arr.append((zeros,ones))
returnprocess1(arr,0,m,n)
defprocess1(arr,i,z,o):
ifi==len(arr):
return0
p1=process1(arr,i+1,z,o)
p2=0
ifarr[i][0]<=zandarr[i][1]<=o:
p2=1+process1(arr,i+1,z-arr[i][0],o-arr[i][1])
ifp1>p2:
returnp1
returnp2
deffind_max_form2(strs,m,n):
length=len(strs)
arr=[]
foriinrange(length):
zeros,ones=zero_and_one(strs[i])
arr.append((zeros,ones))
dp=[[[-1]*(n+1)for_inrange(m+1)]for_inrange(length)]
returnprocess2(arr,0,m,n,dp)
defprocess2(arr,i,z,o,dp):
ifi==len(arr):
return0
ifdp[i][z][o]!=-1:
returndp[i][z][o]
p1=process2(arr,i+1,z,o,dp)
p2=0
ifarr[i][0]<=zandarr[i][1]<=o:
p2=1+process2(arr,i+1,z-arr[i][0],o-arr[i][1],dp)
ans=p1
ifp2>p1:
ans=p2
dp[i][z][o]=ans
returnans
deffind_max_form3(strs,m,n):
length=len(strs)
dp=[[[0]*(n+1)for_inrange(m+1)]for_inrange(length+1)]
foriinrange(length-1,-1,-1):
zeros,ones=zero_and_one(strs[i])
forzinrange(m+1):
foroinrange(n+1):
dp[i][z][o]=dp[i+1][z][o]
ifzeros<=zandones<=o:
dp[i][z][o]=max(dp[i][z][o],1+dp[i+1][z-zeros][o-ones])
returndp[0][m][n]
deffind_max_form4(strs,m,n):
dp=[[0]*(n+1)for_inrange(m+1)]
forsinstrs:
zeros,ones=zero_and_one(s)
foriinrange(m,zeros-1,-1):
forjinrange(n,ones-1,-1):
dp[i][j]=max(dp[i][j],dp[i-zeros][j-ones]+1)
returndp[m][n]
strs=["10","0001","111001","1","0"]
m=5
n=3
res1=find_max_form1(strs,m,n)
print("findMaxForm1:",res1)
res2=find_max_form2(strs,m,n)
print("findMaxForm2:",res2)
res3=find_max_form3(strs,m,n)
print("findMaxForm3:",res3)
res4=find_max_form4(strs,m,n)
print("findMaxForm4:",res4)