2024-03-30：用go语言，集团里有 n 名员工，他们可以完成各种各

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: 使用了三维数组，空间复杂度为 O(m * n * minProfit)。
• dp
  • •profitableSchemes3: 使用了二维数组，空间复杂度为 O(n * minProfit)。
• dp

Go完整代码如下：

packagemain
import"fmt"
funcprofitableSchemes1(nint,minProfitint,group[]int,profit[]int)int{
returnf1(group,profit,0,n,minProfit)
}
funcf1(g[]int,p[]int,iint,rint,sint)int{
ifr<=0{
ifs<=0{
return1
}else{
return0
}
}
ifi==len(g){
ifs<=0{
return1
}else{
return0
}
}
p1:=f1(g,p,i+1,r,s)
p2:=0
ifg[i]<=r{
p2=f1(g,p,i+1,r-g[i],s-p[i])
}
returnp1+p2
}
varmod=1000000007
funcprofitableSchemes2(nint,minProfitint,group[]int,profit[]int)int{
m:=len(group)
dp:=make([][][]int,m)
fora:=0;adp[a]=make([][]int,n+1)
forb:=0;b<=n;b++{
dp[a][b]=make([]int,minProfit+1)
forc:=0;c<=minProfit;c++{
dp[a][b][c]=-1
}
}
}
returnf2(group,profit,0,n,minProfit,dp)
}
funcf2(g[]int,p[]int,iint,rint,sint,dp[][][]int)int{
ifr<=0{
ifs==0{
return1
}else{
return0
}
}
ifi==len(g){
ifs==0{
return1
}else{
return0
}
}
ifdp[i][r][s]!=-1{
returndp[i][r][s]
}
p1:=f2(g,p,i+1,r,s,dp)
p2:=0
ifg[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
returnans
}
funcmax(x,yint)int{
ifx>y{
returnx
}
returny
}
funcprofitableSchemes3(nint,minProfitint,group[]int,profit[]int)int{
dp:=make([][]int,n+1)
forr:=0;r<=n;r++{
dp[r]=make([]int,minProfit+1)
dp[r][0]=1
}
m:=len(group)
fori:=m-1;i>=0;i--{
forr:=n;r>=0;r--{
fors:=minProfit;s>=0;s--{
p1:=dp[r][s]
p2:=0
ifgroup[i]<=r{
p2=dp[r-group[i]][max(0,s-profit[i])]
}
dp[r][s]=(p1+p2)%mod
}
}
}
returndp[n][minProfit]
}
funcmain(){
n:=5
minProfit:=3
group:=[]int{2,2}
profit:=[]int{2,3}
result1:=profitableSchemes1(n,minProfit,group,profit)
fmt.Println("ResultusingprofitableSchemes1:",result1)
result2:=profitableSchemes2(n,minProfit,group,profit)
fmt.Println("ResultusingprofitableSchemes2:",result2)
result3:=profitableSchemes3(n,minProfit,group,profit)
fmt.Println("ResultusingprofitableSchemes3:",result3)
}