golang刷leetcode動態(tài)規(guī)劃之如何解決盈利計劃問題

這篇文章主要介紹了golang刷leetcode動態(tài)規(guī)劃之如何解決盈利計劃問題，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

成都創(chuàng)新互聯(lián)服務(wù)項目包括招遠網(wǎng)站建設(shè)、招遠網(wǎng)站制作、招遠網(wǎng)頁制作以及招遠網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，招遠網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到招遠省份的部分城市，未來相信會繼續(xù)擴大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

幫派里有 G 名成員，他們可能犯下各種各樣的罪行。

第 i 種犯罪會產(chǎn)生 profit[i] 的利潤，它要求 group[i] 名成員共同參與。

讓我們把這些犯罪的任何子集稱為盈利計劃，該計劃至少產(chǎn)生 P 的利潤。

有多少種方案可以選擇？因為答案很大，所以返回它模 10^9 + 7 的值。

示例 1：

輸入：G = 5, P = 3, group = [2,2], profit = [2,3]

輸出：2

解釋： 

至少產(chǎn)生 3 的利潤，該幫派可以犯下罪 0 和罪 1 ，或僅犯下罪 1 。

總的來說，有兩種方案。

示例 2:

輸入：G = 10, P = 5, group = [2,3,5], profit = [6,7,8]

輸出：7

解釋：

至少產(chǎn)生 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.題目要求是統(tǒng)計利潤至少為 P，且人數(shù)最多為 G 的方案數(shù)。由于利潤最多有可能達到 100 * n，數(shù)據(jù)范圍過大而不方便進行動態(tài)規(guī)劃，可以考慮該問題的對偶問題。即統(tǒng)計人數(shù)最多為 G 的方案數(shù)，減去利潤小于 P，且統(tǒng)計人數(shù)最多為 G 的方案數(shù)。2.對于第一部分，動態(tài)規(guī)劃的狀態(tài)為 s(i,j)，表示考慮了前 i 個計劃，參與人數(shù)為 j 的方案數(shù)是多少。對于第 i 個計劃，s(i,j)=s(i,j)+s(i?1,j?group[i])。初始值 s(0,0)=1。人數(shù)最多為 G 的方案數(shù)為 ∑Gj=0s(n,j)。實際上可以省略掉第一維。3,對于第二部分，動態(tài)規(guī)劃的狀態(tài)為 f(i,j,k)，表示考慮了前 i 個計劃，參與人數(shù)為 j 的方案數(shù)，且利潤為 k 的方案數(shù)是多少。對于第 i 個計劃，f(i,j,k)=f(i,j,k)+f(i?1,j?group[i],k?profit[i])。初始值 f(0,0,0)=1。利潤小于 P，且統(tǒng)計人數(shù)最多為 G 的方案數(shù)為 ∑j<=G,k<Pj=k=0f(n,j,k)。實際上可以仍然省略掉第一維。4.最終答案就是兩部分做差。5.為了防止中間結(jié)果溢出，每次計算都要取摸6.由于取摸了，所以結(jié)果可能是負值，所以要加摸

源碼：

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動態(tài)規(guī)劃之如何解決盈利計劃問題”這篇文章對大家有幫助，同時也希望大家多多支持創(chuàng)新互聯(lián)，關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，更多相關(guān)知識等著你來學(xué)習(xí)!

網(wǎng)站題目：golang刷leetcode動態(tài)規(guī)劃之如何解決盈利計劃問題
URL網(wǎng)址：http://bm7419.com/article18/jcejgp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供動態(tài)網(wǎng)站、虛擬主機、電子商務(wù)、小程序開發(fā)、網(wǎng)站收錄、定制開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)