2024-03-27：用go语言，多维费用背包。 给你一个二进制字符串数组 strs 和两个整数 m 和 n， 请你找出并返回
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.findMaxForm1函数使用递归的方式实现。它遍历字符串数组strs，将每个字符串中0和1的数量存储在一个二维数组arr中。然后通过递归函数process1进行计算，不断比较所选字符串是否符合要求，选择放入或不放入子集。该方法的时间复杂度为O(2^n)，空间复杂度为O(n)。
2.findMaxForm2函数使用记忆化搜索的方式实现。它也遍历字符串数组strs得到二维数组arr，但使用三维数组dp进行记忆化，记录已经计算过的结果，避免重复计算。该方法的时间复杂度为O(m * n * len(strs))，空间复杂度为O(m * n * len(strs))。
3.findMaxForm3函数使用动态规划的方式实现。它从后向前遍历字符串数组strs，得到二维数组dp来保存计算结果。通过比较选择当前字符串加入子集还是不加入子集，并更新动态规划数组dp。该方法的时间复杂度为O(m * n * len(strs))，空间复杂度为O(m * n * len(strs))。
4findMaxForm4函数使用动态规划的方式实现。它遍历字符串数组strs，得到二维数组dp来保存计算结果。使用一维数组dp进行滚动更新，从后向前遍历，根据当前字符串的0和1的数量，更新动态规划数组dp。该方法的时间复杂度为O(m * n * len(strs))，空间复杂度为O(m * n)。
总时间复杂度：O(m * n * len(strs))
总额外空间复杂度：O(m * n * len(strs))
Go完整代码如下：
package?main
import?(
"fmt"
)
var?zeros,?ones?int
func?findMaxForm1(strs?[]string,?m?int,?n?int)?int?{
len?:=?len(strs)
arr?:=?make([][]int,?len)
for?i?:=?0;?i?<?len;?i++?{
zeroAndOne(strs[i])
arr[i]?=?[]int{zeros,?ones}
}
return?process1(arr,?0,?m,?n)
}
func?process1(arr?[][]int,?i?int,?z?int,?o?int)?int?{
if?i?==?len(arr)?{
return?0
}
p1?:=?process1(arr,?i+1,?z,?o)
p2?:=?0
if?arr[i][0]?<=?z?&&?arr[i][1]?<=?o?{
p2?=?1?+?process1(arr,?i+1,?z-arr[i][0],?o-arr[i][1])
}
if?p1?>?p2?{
return?p1
}
return?p2
}
func?findMaxForm2(strs?[]string,?m?int,?n?int)?int?{
len?:=?len(strs)
arr?:=?make([][]int,?len)
for?i?:=?0;?i?<?len;?i++?{
zeroAndOne(strs[i])
arr[i]?=?[]int{zeros,?ones}
}
dp?:=?make([][][]int,?len)
for?i?:=?0;?i?<?len;?i++?{
dp[i]?=?make([][]int,?m+1)
for?j?:=?0;?j?<=?m;?j++?{
dp[i][j]?=?make([]int,?n+1)
for?k?:=?0;?k?<=?n;?k++?{
dp[i][j][k]?=?-1
}
}
}
return?process2(arr,?0,?m,?n,?dp)
}
func?process2(arr?[][]int,?i?int,?z?int,?o?int,?dp?[][][]int)?int?{
if?i?==?len(arr)?{
return?0
}
if?dp[i][z][o]?!=?-1?{
return?dp[i][z][o]
}
p1?:=?process2(arr,?i+1,?z,?o,?dp)
p2?:=?0
if?arr[i][0]?<=?z?&&?arr[i][1]?<=?o?{
p2?=?1?+?process2(arr,?i+1,?z-arr[i][0],?o-arr[i][1],?dp)
}
ans?:=?p1
if?p2?>?p1?{
ans?=?p2
}
dp[i][z][o]?=?ans
return?ans
}
func?findMaxForm3(strs?[]string,?m?int,?n?int)?int?{
len0?:=?len(strs)
dp?:=?make([][][]int,?len0+1)
for?i?:=?len0;?i?>=?0;?i--?{
dp[i]?=?make([][]int,?m+1)
for?z?:=?0;?z?<=?m;?z++?{
dp[i][z]?=?make([]int,?n+1)
}
}
for?i?:=?len0?-?1;?i?>=?0;?i--?{
zeroAndOne(strs[i])
for?z?:=?0;?z?<=?m;?z++?{
for?o?:=?0;?o?<=?n;?o++?{
dp[i][z][o]?=?dp[i+1][z][o]
if?zeros?<=?z?&&?ones?<=?o?{
dp[i][z][o]?=?max(dp[i][z][o],?1+dp[i+1][z-zeros][o-ones])
}
}
}
}
return?dp[0][m][n]
}
func?zeroAndOne(str?string)?{
zeros?=?0
ones?=?0
for?i?:=?0;?i?<?len(str);?i++?{
if?str[i]?==?'0'?{
zeros++
}?else?{
ones++
}
}
}
func?findMaxForm4(strs?[]string,?m?int,?n?int)?int?{
dp?:=?make([][]int,?m+1)
for?i?:=?0;?i?<=?m;?i++?{
dp[i]?=?make([]int,?n+1)
}
for?_,?s?:=?range?strs?{
zeroAndOne(s)
for?i?:=?m;?i?>=?zeros;?i--?{
for?j?:=?n;?j?>=?ones;?j--?{
dp[i][j]?=?max(dp[i][j],?dp[i-zeros][j-ones]+1)
}
}
}
return?dp[m][n]
}
func?max(a,?b?int)?int?{
if?a?>?b?{
return?a
}
return?b
}
func?main()?{
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-*-
def?zero_and_one(string):
zeros?=?0
ones?=?0
for?char?in?string:
if?char?==?'0':
zeros?+=?1
else:
ones?+=?1
return?zeros,?ones
def?find_max_form1(strs,?m,?n):
length?=?len(strs)
arr?=?[]
for?i?in?range(length):
zeros,?ones?=?zero_and_one(strs[i])
arr.append((zeros,?ones))
return?process1(arr,?0,?m,?n)
def?process1(arr,?i,?z,?o):
if?i?==?len(arr):
return?0
p1?=?process1(arr,?i+1,?z,?o)
p2?=?0
if?arr[i][0]?<=?z?and?arr[i][1]?<=?o:
p2?=?1?+?process1(arr,?i+1,?z-arr[i][0],?o-arr[i][1])
if?p1?>?p2:
return?p1
return?p2
def?find_max_form2(strs,?m,?n):
length?=?len(strs)
arr?=?[]
for?i?in?range(length):
zeros,?ones?=?zero_and_one(strs[i])
arr.append((zeros,?ones))
dp?=?[[[-1]?*?(n+1)?for?_?in?range(m+1)]?for?_?in?range(length)]
return?process2(arr,?0,?m,?n,?dp)
def?process2(arr,?i,?z,?o,?dp):
if?i?==?len(arr):
return?0
if?dp[i][z][o]?!=?-1:
return?dp[i][z][o]
p1?=?process2(arr,?i+1,?z,?o,?dp)
p2?=?0
if?arr[i][0]?<=?z?and?arr[i][1]?<=?o:
p2?=?1?+?process2(arr,?i+1,?z-arr[i][0],?o-arr[i][1],?dp)
ans?=?p1
if?p2?>?p1:
ans?=?p2
dp[i][z][o]?=?ans
return?ans
def?find_max_form3(strs,?m,?n):
length?=?len(strs)
dp?=?[[[0]?*?(n+1)?for?_?in?range(m+1)]?for?_?in?range(length+1)]
for?i?in?range(length-1,?-1,?-1):
zeros,?ones?=?zero_and_one(strs[i])
for?z?in?range(m+1):
for?o?in?range(n+1):
dp[i][z][o]?=?dp[i+1][z][o]
if?zeros?<=?z?and?ones?<=?o:
dp[i][z][o]?=?max(dp[i][z][o],?1?+?dp[i+1][z-zeros][o-ones])
return?dp[0][m][n]
def?find_max_form4(strs,?m,?n):
dp?=?[[0]?*?(n+1)?for?_?in?range(m+1)]
for?s?in?strs:
zeros,?ones?=?zero_and_one(s)
for?i?in?range(m,?zeros-1,?-1):
for?j?in?range(n,?ones-1,?-1):
dp[i][j]?=?max(dp[i][j],?dp[i-zeros][j-ones]+1)
return?dp[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)
在这里插入图片描述
- 发表于:
- 原文链接：https://page.om.qq.com/page/OqvnceQCDDy1gLQA2mH7OxvA0
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
