溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了golang刷leetcode動態規劃之如何解決盈利計劃問題，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。
幫派里有 G 名成員，他們可能犯下各種各樣的罪行。
第 i 種犯罪會產生 profit[i] 的利潤，它要求 group[i] 名成員共同參與。
讓我們把這些犯罪的任何子集稱為盈利計劃，該計劃至少產生 P 的利潤。
有多少種方案可以選擇？因為答案很大，所以返回它模 10^9 + 7 的值。
示例 1：
輸入：G = 5, P = 3, group = [2,2], profit = [2,3]
輸出：2
解釋：
至少產生 3 的利潤，該幫派可以犯下罪 0 和罪 1 ，或僅犯下罪 1 。
總的來說，有兩種方案。
示例 2:
輸入：G = 10, P = 5, group = [2,3,5], profit = [6,7,8]
輸出：7
解釋：
至少產生 5 的利潤，只要他們犯其中一種罪就行，所以該幫派可以犯下任何罪行 。
有 7 種可能的計劃：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。
提示：
1 <= G <= 100
0 <= P <= 100
1 <= group[i] <= 100
0 <= profit[i] <= 100
1 <= group.length = profit.length <= 100
解題思路：
1.題目要求是統計利潤至少為 P，且人數最多為 G 的方案數。由于利潤最多有可能達到 100 * n，數據范圍過大而不方便進行動態規劃，可以考慮該問題的對偶問題。即統計人數最多為 G 的方案數，減去利潤小于 P，且統計人數最多為 G 的方案數。2.對于第一部分，動態規劃的狀態為 s(i,j)，表示考慮了前 i 個計劃，參與人數為 j 的方案數是多少。對于第 i 個計劃，s(i,j)=s(i,j)+s(i?1,j?group[i])。初始值 s(0,0)=1。人數最多為 G 的方案數為 ∑Gj=0s(n,j)。實際上可以省略掉第一維。3,對于第二部分，動態規劃的狀態為 f(i,j,k)，表示考慮了前 i 個計劃，參與人數為 j 的方案數，且利潤為 k 的方案數是多少。對于第 i 個計劃，f(i,j,k)=f(i,j,k)+f(i?1,j?group[i],k?profit[i])。初始值 f(0,0,0)=1。利潤小于 P，且統計人數最多為 G 的方案數為 ∑j<=G,k<Pj=k=0f(n,j,k)。實際上可以仍然省略掉第一維。4.最終答案就是兩部分做差。5.為了防止中間結果溢出，每次計算都要取摸6.由于取摸了，所以結果可能是負值，所以要加摸
源碼：
func profitableSchemes(G int, P int, group []int, profit []int) int { mod := 1000000007 n:=len(group) s:=make([]int,G+1) s[0]=1 for i:=0;i<n;i++{ for j:=G;j>=group[i];j--{ //s[i,j]=s[i,j]+s[i-1,j-group[i]] s[j]=(s[j]+s[j-group[i]])%mod } } f:=make([][]int,G+1) for i:=0;i<=G;i++{ f[i]=make([]int,P+1) } f[0][0]=1 for i:=0;i<n;i++{ for j:=G;j>=group[i];j--{ for k:=P-1;k>=profit[i];k--{ //f[i,j,k]=f[i,j,k]+f[i-1,j-group[i],k-profit[i]] f[j][k]=(f[j][k]+f[j-group[i]][k-profit[i]])%mod } } } ss:=0 for j:=0;j<=G;j++{ ss=(ss+s[j])%mod } ff:=0 for j:=0;j<=G;j++{ for k:=0;k<P;k++{ ff=(ff+f[j][k])%mod } } return (ss-ff+mod)%mod}
感謝你能夠認真閱讀完這篇文章，希望小編分享的“golang刷leetcode動態規劃之如何解決盈利計劃問題”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
