2024-03-30：用go语言，集团里有 n 名员工，他们可以完成各种各样的工作创造利润，第 i 种工作会产生 profit

福大大架构师每日一题

发布于 2024-04-11 20:31:05

980

发布于 2024-04-11 20:31:05

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2024-03-30：用go语言，集团里有 n 名员工，他们可以完成各种各样的工作创造利润，

第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与，

如果成员参与了其中一项工作，就不能参与另一项工作，

工作的任何至少产生 minProfit 利润的子集称为盈利计划，

并且工作的成员总数最多为 n。

有多少种计划可以选择？因为答案很大，所以返回结果模 10^9 + 7 的值。

输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]。

输出：2。

答案2024-03-30：

来自左程云。

灵捷3.5

大体步骤如下：

这三种算法都解决了一个问题，即在给定一组工作和利润以及员工的人数限制下，找出满足最低利润要求的盈利计划数量。以下是它们的大体过程：

profitableSchemes1:

1.递归函数 f1 对组合进行深度优先搜索，尝试每种工作的所有可能性，以达到满足最低利润要求的盈利计划。

2.检查每种工作是否满足人数限制，并计算利润是否达到最低要求。

3.返回满足条件的计划数量。

profitableSchemes2:

1.使用动态规划方法，创建三维数组 dp 以保存中间结果。

2.递归函数 f2 逐步填充 dp 数组，记录以当前工作和利润数为基础时的计划数量。

3.每次计算时检查数组中是否已有记录，避免重复计算。

4.返回最终计划数量。

profitableSchemes3:

1.同样采用动态规划，但只使用二维数组 dp，减少额外空间的使用。

2.从最后一个工作向前逐步计算满足条件的计划数量。

3.根据当前工作是否选择、人数是否足够、利润是否达标，更新动态规划数组中的值。

4.最终输出满足条件的计划数量。

复杂度分析:

• 时间复杂度：
- • profitableSchemes1: 由于是基于递归的深度优先搜索，时间复杂度较高，为指数级别，取决于工作数量和员工人数。
- • profitableSchemes2: 使用了动态规划并记录了每个可能情况，时间复杂度为 O(m * n * minProfit)，m 为工作数量，n 为员工人数。
- • profitableSchemes3: 类似于第二种算法，但只使用了二维数组，时间复杂度也为 O(m * n * minProfit)。
• 空间复杂度：
- • profitableSchemes1: 仅有递归调用的栈空间，空间复杂度取决于递归深度。
- • profitableSchemes2: 使用了三维数组 dp，空间复杂度为 O(m * n * minProfit)。
- • profitableSchemes3: 使用了二维数组 dp，空间复杂度为 O(n * minProfit)。

Go完整代码如下：

package main

import "fmt"

func profitableSchemes1(n int, minProfit int, group []int, profit []int) int {
    return f1(group, profit, 0, n, minProfit)
}

func f1(g []int, p []int, i int, r int, s int) int {
    if r <= 0 {
        if s <= 0 {
            return 1
        } else {
            return 0
        }
    }
    if i == len(g) {
        if s <= 0 {
            return 1
        } else {
            return 0
        }
    }
    p1 := f1(g, p, i+1, r, s)
    p2 := 0
    if g[i] <= r {
        p2 = f1(g, p, i+1, r-g[i], s-p[i])
    }
    return p1 + p2
}

var mod = 1000000007

func profitableSchemes2(n int, minProfit int, group []int, profit []int) int {
    m := len(group)
    dp := make([][][]int, m)
    for a := 0; a < m; a++ {
        dp[a] = make([][]int, n+1)
        for b := 0; b <= n; b++ {
            dp[a][b] = make([]int, minProfit+1)
            for c := 0; c <= minProfit; c++ {
                dp[a][b][c] = -1
            }
        }
    }
    return f2(group, profit, 0, n, minProfit, dp)
}

func f2(g []int, p []int, i int, r int, s int, dp [][][]int) int {
    if r <= 0 {
        if s == 0 {
            return 1
        } else {
            return 0
        }
    }
    if i == len(g) {
        if s == 0 {
            return 1
        } else {
            return 0
        }
    }
    if dp[i][r][s] != -1 {
        return dp[i][r][s]
    }
    p1 := f2(g, p, i+1, r, s, dp)
    p2 := 0
    if g[i] <= r {
        p2 = f2(g, p, i+1, r-g[i], max(0, s-p[i]), dp)
    }
    ans := (p1 + p2) % mod
    dp[i][r][s] = ans
    return ans
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func profitableSchemes3(n int, minProfit int, group []int, profit []int) int {
    dp := make([][]int, n+1)
    for r := 0; r <= n; r++ {
        dp[r] = make([]int, minProfit+1)
        dp[r][0] = 1
    }
    m := len(group)
    for i := m - 1; i >= 0; i-- {
        for r := n; r >= 0; r-- {
            for s := minProfit; s >= 0; s-- {
                p1 := dp[r][s]
                p2 := 0
                if group[i] <= r {
                    p2 = dp[r-group[i]][max(0, s-profit[i])]
                }
                dp[r][s] = (p1 + p2) % mod
            }
        }
    }
    return dp[n][minProfit]
}

func main() {
    n := 5
    minProfit := 3
    group := []int{2, 2}
    profit := []int{2, 3}

    result1 := profitableSchemes1(n, minProfit, group, profit)
    fmt.Println("Result using profitableSchemes1:", result1)

    result2 := profitableSchemes2(n, minProfit, group, profit)
    fmt.Println("Result using profitableSchemes2:", result2)

    result3 := profitableSchemes3(n, minProfit, group, profit)
    fmt.Println("Result using profitableSchemes3:", result3)
}