golang刷leetcode动态规划之如何解决盈利计划问题
发表于:2024-09-21 作者:千家信息网编辑
千家信息网最后更新 2024年09月21日,这篇文章主要介绍了golang刷leetcode动态规划之如何解决盈利计划问题,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。帮派里有
千家信息网最后更新 2024年09月21日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动态规划之如何解决盈利计划问题"这篇文章对大家有帮助,同时也希望大家多多支持,关注行业资讯频道,更多相关知识等着你来学习!
方案
利润
人数
动态
规划
问题
篇文章
统计
盈利
帮派
实际
实际上
成员
状态
示例
答案
结果
罪行
一维
犯罪
数据库的安全要保护哪些东西
数据库安全各自的含义是什么
生产安全数据库录入
数据库的安全性及管理
数据库安全策略包含哪些
海淀数据库安全审计系统
建立农村房屋安全信息数据库
易用的数据库客户端支持安全管理
连接数据库失败ssl安全错误
数据库的锁怎样保障安全
浙江省网络安全知识试题
上海蛙扑网络技术有限公司口碑
2021网络安全法专场竞赛
河北大学网络技术中心电话
一个服务器挂多个网站
在自己的网络里无法连接服务器
云等云服务器数据安全
数据库基础与实践技术第八章
北京聚搏时代网络技术
无锡域名服务器
网络安全信息化检查考核
网络安全法侵害个人信息罚款
全球重症数据库
还原数据库如何不要日志
东兴租房网络安全
网络安全的五个重点
access数据库下载2010
长沙洋飒网络技术
数据库可视化工具开源的
网络安全法认为从网络安全的
天融信网络技术安全有限公司
网站服务器能放电脑里吗
述软件开发周期或过程
服务器加密中转
数据库商品库存信息管理er图
wpf不用数据库如何存储数据
网络安全团队都有哪些人
迷你数据库如何加密
网络安全是干什么的累吗
安卓软件开发合同