写点什么

2024-03-30:用 go 语言,集团里有 n 名员工,他们可以完成各种各样的工作创造利润, 第 i 种工作会产生 profit[i] 的利润,它要求 group[i] 名成员共同参与, 如果成员参与

  • 2024-03-30
    北京
  • 本文字数:2281 字

    阅读完需:约 7 分钟

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)}
复制代码



发布于: 刚刚阅读数: 5
用户头像

公众号:福大大架构师每日一题 2021-02-15 加入

公众号:福大大架构师每日一题

评论

发布
暂无评论
2024-03-30:用go语言,集团里有 n 名员工,他们可以完成各种各样的工作创造利润, 第 i 种工作会产生 profit[i] 的利润,它要求 group[i] 名成员共同参与, 如果成员参与_福大大架构师每日一题_福大大架构师每日一题_InfoQ写作社区