golang刷leetcode动态规划之如何解决盈利计划问题

这篇文章主要介绍了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 

源码:

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=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=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 

感谢你能够认真阅读完这篇文章,希望小编分享的“golang刷leetcode动态规划之如何解决盈利计划问题”这篇文章对大家有帮助,同时也希望大家多多支持创新互联,关注创新互联行业资讯频道,更多相关知识等着你来学习!


当前题目:golang刷leetcode动态规划之如何解决盈利计划问题
标题URL:http://myzitong.com/article/jcejgp.html