2024-03-30:用 go 语言,集团里有 n 名员工,他们可以完成各种各样的工作创造利润, 第 i 种工作会产生 profit[i] 的利润,它要求 group[i] 名成员共同参与, 如果成员参与
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:
来自左程云。
大体步骤如下:
这三种算法都解决了一个问题,即在给定一组工作和利润以及员工的人数限制下,找出满足最低利润要求的盈利计划数量。以下是它们的大体过程:
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 完整代码如下:
版权声明: 本文为 InfoQ 作者【福大大架构师每日一题】的原创文章。
原文链接:【http://xie.infoq.cn/article/f133b07ecc63e4555f86e6259】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
评论