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)

在这里插入图片描述