2024-03-27：用 go 语言，多维费用背包。给你一个二进制字符串数组 strs 和两个整数 m 和 n，请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个

作者：福大大架构师每日一题

2024-03-27
北京
本文字数：3378 字
阅读完需：约 11 分钟

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))。

4 findMaxForm4 函数使用动态规划的方式实现。它遍历字符串数组 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 = 5n = 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)