879. 盈利計(jì)劃

本題與經(jīng)典背包問(wèn)題非常相似。兩者不同點(diǎn)在于經(jīng)典背包問(wèn)題只有一種容量限制，而本題卻有兩種限制：集團(tuán)員工人數(shù)上限 n，以及工作產(chǎn)生的利潤(rùn)下限 minProfit。

通過(guò)經(jīng)典背包問(wèn)題的練習(xí)，我們已知經(jīng)典背包問(wèn)題可以使用二維動(dòng)態(tài)規(guī)劃求解：兩個(gè)維度分別代表物品和容量的限制標(biāo)準(zhǔn)。

對(duì)于本題上述的兩種限制，我們可以想到使用三維動(dòng)態(tài)規(guī)劃求解。

本題解法的三個(gè)維度分別為：當(dāng)前可選擇的工作，已選擇的小組員工人數(shù)，以及目前狀態(tài)的工作獲利下限。

根據(jù)上述分析，我們可以定義一個(gè)三維數(shù)組 dp 作為動(dòng)態(tài)規(guī)劃的狀態(tài)，其中 dp[i][j][k] 表示在前 i 個(gè)工作中選擇了 j 個(gè)員工，并且滿足工作利潤(rùn)至少為 k 的情況下的盈利計(jì)劃的總數(shù)目。假設(shè) group 數(shù)組長(zhǎng)度為 len，那么不考慮取模運(yùn)算的情況下，最終答案為：

所以我們可以新建一個(gè)三維數(shù)組 dp[len+1][n+1][minProfit+1]，初始化 dp[0][0][0]=1。接下來(lái)分析狀態(tài)轉(zhuǎn)移方程，對(duì)于每個(gè)工作 i，我們根據(jù)當(dāng)前工作人數(shù)上限 j，有能夠開(kāi)展當(dāng)前工作和無(wú)法開(kāi)展當(dāng)前工作兩種情況：

• 如果無(wú)法開(kāi)展當(dāng)前工作 i，那么顯然：
  
• 如果能夠開(kāi)展當(dāng)前工作 i，設(shè)當(dāng)前小組人數(shù)為 group[i]，工作獲利為 profit[i]，那么不考慮取模運(yùn)算的情況下，則有：

由于我們定義的第三維是工作利潤(rùn)至少為 k 而不是 工作利潤(rùn)恰好為 k，因此上述狀態(tài)轉(zhuǎn)移方程中右側(cè)的第三維是 max(0,k?profit[i]) 而不是 k?profit[i]。讀者可以思考這一步的妙處所在。

Code

Python

class Solution:def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:MOD = 10 ** 9 + 7length = len(group)dp = [[[0] * (minProfit + 1) for _ in range(n + 1)] for _ in range(length + 1)]dp[0][0][0] = 1for i in range(1, length + 1):# 第 i 個(gè)工作要求參與的員工數(shù)量和會(huì)產(chǎn)生的利潤(rùn)members, earn = group[i - 1], profit[i - 1]for j in range(n + 1):for k in range(minProfit + 1):if j < members: # 如果當(dāng)前工作人數(shù)上限小于需要求參與的員工數(shù)量則無(wú)法開(kāi)展此工作dp[i][j][k] = dp[i - 1][j][k]else:dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][j - members][max(0, k - earn)]) % MODtotal = sum(dp[length][j][minProfit] for j in range(n + 1))return total % MOD

作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/profitable-schemes/solution/ying-li-ji-hua-by-leetcode-solution-3t8o/
來(lái)源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

總結(jié)

以上是生活随笔為你收集整理的LeetCode 879. 盈利计划的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。