【动态规划】879. 盈利计划

这篇具有很好参考价值的文章主要介绍了【动态规划】879. 盈利计划。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

作者推荐

【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径

本文涉及知识点

动态规划汇总

LeetCode879. 盈利计划

集团里有 n 名员工,他们可以完成各种各样的工作创造利润。
第 i 种工作会产生 profit[i] 的利润,它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作,就不能参与另一项工作。
工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。
有多少种计划可以选择?因为答案很大,所以 返回结果模 10^9 + 7 的值。
示例 1:
输入:n = 5, minProfit = 3, group = [2,2], profit = [2,3]
输出:2
解释:至少产生 3 的利润,该集团可以完成工作 0 和工作 1 ,或仅完成工作 1 。
总的来说,有两种计划。
示例 2:
输入:n = 10, minProfit = 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 <= n <= 100
0 <= minProfit <= 100
1 <= group.length <= 100
1 <= group[i] <= 100
profit.length == group.length
0 <= profit[i] <= 100

动态规划

动态规划的状态表示

pre[j][k]表示 从前i个工作中,完成若干任务,出动了j人,利润为k的盈利计划数。例外:k==minProfit 时,包括利润大于minProfit的盈利计划数。

动态规划的转移方程

前i个任务,出动 preCount 人,利润为p
{ d p [ p r e C o u n t ] [ p ] + = p r e [ p r e C o u n t ] [ p ] 不完成本任务 人数不足无法完成当前任务 p r e C o u n t + g r o u p [ i ] > n d p [ p r e C o u n t + g r o u p [ i ] ] [ m i n ( m i n P r o f i t , p + p r o f i t [ i ] ) ] + = p r e [ p r e C o u n t ] [ p ] 完成本任务 \begin{cases} dp[preCount][p] += pre[preCount][p] & 不完成本任务 \\ 人数不足无法完成当前任务 & preCount+group[i] >n \\ dp[preCount+group[i]][min(minProfit,p+profit[i])] +=pre[preCount][p] & 完成本任务 \\ \end{cases} dp[preCount][p]+=pre[preCount][p]人数不足无法完成当前任务dp[preCount+group[i]][min(minProfit,p+profit[i])]+=pre[preCount][p]不完成本任务preCount+group[i]>n完成本任务

动态规划的初始值

pre[0][0]=1

动态规划的填表顺序

i从小到大

动态规划的返回值

∑ i : 0 p r e . s i z e ( ) − 1 \sum\Large_{i:0 }^{pre.size()-1} i:0pre.size()1v[i].back()

代码

核心代码

template<int MOD = 1000000007>
class C1097Int
{
public:
	C1097Int(long long llData = 0) :m_iData(llData% MOD)
	{

	}
	C1097Int  operator+(const C1097Int& o)const
	{
		return C1097Int(((long long)m_iData + o.m_iData) % MOD);
	}
	C1097Int& operator+=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData + o.m_iData) % MOD;
		return *this;
	}
	C1097Int& operator-=(const C1097Int& o)
	{
		m_iData = (m_iData + MOD - o.m_iData) % MOD;
		return *this;
	}
	C1097Int  operator-(const C1097Int& o)
	{
		return C1097Int((m_iData + MOD - o.m_iData) % MOD);
	}
	C1097Int  operator*(const C1097Int& o)const
	{
		return((long long)m_iData * o.m_iData) % MOD;
	}
	C1097Int& operator*=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData * o.m_iData) % MOD;
		return *this;
	}
	bool operator<(const C1097Int& o)const
	{
		return m_iData < o.m_iData;
	}
	C1097Int pow(long long n)const
	{
		C1097Int iRet = 1, iCur = *this;
		while (n)
		{
			if (n & 1)
			{
				iRet *= iCur;
			}
			iCur *= iCur;
			n >>= 1;
		}
		return iRet;
	}
	C1097Int PowNegative1()const
	{
		return pow(MOD - 2);
	}
	int ToInt()const
	{
		return m_iData;
	}
private:
	int m_iData = 0;;
};

class Solution {
public:
	int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
		vector<vector<C1097Int<>>> pre(n + 1, vector<C1097Int<>>(minProfit + 1));
		pre[0][0] = 1;
		for (int i = 0; i < group.size(); i++)
		{
			auto dp = pre;//不完成当前任务
			for (int preCount = 0; preCount < n; preCount++)
			{
				for (int p = 0; p <= minProfit; p++)
				{
					const int iNewCount = preCount + group[i];
					if (iNewCount > n)
					{
						continue;
					}
					const int iNewProfit = min(minProfit, p + profit[i]);
					dp[iNewCount][iNewProfit] += pre[preCount][p];
				}
			}
			pre.swap(dp);
		}
		C1097Int<> biRet;
		for (const auto& v : pre)
		{
			biRet += v.back();
		}
		return biRet.ToInt();
	}
};

测试用例


template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{	
	int n,  minProfit;
	vector<int> group, profit;
	{
		Solution sln;
		n = 5, minProfit = 3, group = { 2, 2 }, profit = { 2, 3 };
		auto res = sln.profitableSchemes(n, minProfit, group, profit);
		Assert(res, 2);
	}
	{
		Solution sln;
		n = 10, minProfit = 5, group = { 2, 3, 5 }, profit = { 6, 7, 8 };
		auto res = sln.profitableSchemes(n, minProfit, group, profit);
		Assert(res, 7);
	}


}

2023年 1月第一版

class CBigMath
{
public:
static void AddAssignment(int* dst, const int& iSrc)
{
*dst = (dst + iSrc) % s_iMod;
}
static void AddAssignment(int
dst, const int& iSrc, const int& iSrc1)
{
*dst = (*dst + iSrc) % s_iMod;
*dst = (dst + iSrc1) % s_iMod;
}
static void AddAssignment(int
dst, const int& iSrc, const int& iSrc1, const int& iSrc2)
{
*dst = (*dst + iSrc) % s_iMod;
*dst = (*dst + iSrc1) % s_iMod;
*dst = (dst + iSrc2) % s_iMod;
}
static void SubAssignment(int
dst, const int& iSrc)
{
*dst = (s_iMod - iSrc + *dst) % s_iMod;
}
static int Add(const int& iAdd1, const int& iAdd2)
{
return (iAdd1 + iAdd2) % s_iMod;
}
static int Mul(const int& i1, const int& i2)
{
return((long long)i1 i2) % s_iMod;
}
private:
static const int s_iMod = 1000000007;
};
class Solution {
public:
int profitableSchemes(int n, int minProfit, vector& group, vector& profit) {
m_minProfit = minProfit;
vector pre((n + 1)
(minProfit + 1));
pre[0] = 1;
int iMaxN = 0;
int iMaxProfit = 0;
for (int i = 0; i < group.size(); i++)
{
vector dp = pre;
for (int j = 0; j <= iMaxN; j++)
{
for (int k = 0; k <= iMaxProfit; k++)
{
const int iNewN = j + group[i];
if (iNewN > n)
{
//员工不足
continue;
}
const int iNewProfit = min(minProfit, k + profit[i]);
CBigMath::AddAssignment(&dp[GetIndex(iNewN, iNewProfit)], pre[GetIndex(j, k)]);
}
}
pre.swap(dp);
iMaxN = min(n, iMaxN + group[i]);
iMaxProfit = min(minProfit, iMaxProfit + profit[i]);
}
int iNum = 0;
for (int i = 0; i <= iMaxN; i++)
{
CBigMath::AddAssignment(&iNum ,pre[GetIndex(i, minProfit)]);
}
return iNum;
}
inline int GetIndex(int n, int pro)
{
return n *(m_minProfit + 1) + pro;
}
int m_minProfit;
};

2023年1月版

class CBigMath
{
public:
static void AddAssignment(int* dst, const int& iSrc)
{
*dst = (dst + iSrc) % s_iMod;
}
static void AddAssignment(int
dst, const int& iSrc, const int& iSrc1)
{
*dst = (*dst + iSrc) % s_iMod;
*dst = (dst + iSrc1) % s_iMod;
}
static void AddAssignment(int
dst, const int& iSrc, const int& iSrc1, const int& iSrc2)
{
*dst = (*dst + iSrc) % s_iMod;
*dst = (*dst + iSrc1) % s_iMod;
*dst = (dst + iSrc2) % s_iMod;
}
static void SubAssignment(int
dst, const int& iSrc)
{
*dst = (s_iMod - iSrc + *dst) % s_iMod;
}
static int Add(const int& iAdd1, const int& iAdd2)
{
return (iAdd1 + iAdd2) % s_iMod;
}
static int Mul(const int& i1, const int& i2)
{
return((long long)i1 i2) % s_iMod;
}
private:
static const int s_iMod = 1000000007;
};
class Solution {
public:
int profitableSchemes(int n, int minProfit, vector& group, vector& profit) {
m_minProfit = minProfit;
vector pre((n + 1)
(minProfit + 1));
pre[0] = 1;
int iMaxN = 0;
int iMaxProfit = 0;
for (int i = 0; i < group.size(); i++)
{
vector dp = pre;
for (int j = 0; j <= iMaxN; j++)
{
for (int k = 0; k <= iMaxProfit; k++)
{
const int iNewN = j + group[i];
if (iNewN > n)
{
//员工不足
continue;
}
const int iNewProfit = min(minProfit, k + profit[i]);
CBigMath::AddAssignment(&dp[GetIndex(iNewN, iNewProfit)], pre[GetIndex(j, k)]);
}
}
pre.swap(dp);
iMaxN = min(n, iMaxN + group[i]);
iMaxProfit = min(minProfit, iMaxProfit + profit[i]);
}
int iNum = 0;
for (int i = 0; i <= iMaxN; i++)
{
CBigMath::AddAssignment(&iNum ,pre[GetIndex(i, minProfit)]);
}
return iNum;
}
inline int GetIndex(int n, int pro)
{
return n *(m_minProfit + 1) + pro;
}
int m_minProfit;
};

【动态规划】879. 盈利计划,# 算法题,动态规划,算法,c++,LeetCode,盈利计划,利润,员工数

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 **C+

+17**
如无特殊说明,本算法用**C++**实现。

【动态规划】879. 盈利计划,# 算法题,动态规划,算法,c++,LeetCode,盈利计划,利润,员工数文章来源地址https://www.toymoban.com/news/detail-818657.html

到了这里,关于【动态规划】879. 盈利计划的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法】动态规划 ⑦ ( LeetCode 55. 跳跃游戏 | 算法分析 | 代码示例 )

    LeetCode 55. 跳跃游戏 : https://leetcode.cn/problems/jump-game/ 给定一个 非负整数数组 nums ,你最初位于数组的 第一个下标 0 位置 。 数组中的每个元素 代表你在该位置可以 跳跃的最大长度。 判断你 是否能够到达最后一个下标。 给定一个一维数组 , 数组元素不能有负数 , 如 : {2, 2,

    2024年02月10日
    浏览(39)
  • 算法练习Day30 (Leetcode/Python-动态规划)

    62. Unique Paths There is a robot on an  m x n  grid. The robot is initially located at the  top-left corner  (i.e.,  grid[0][0] ). The robot tries to move to the  bottom-right corner  (i.e.,  grid[m - 1][n - 1] ). The robot can only move either down or right at any point in time. Given the two integers  m  and  n , return  the number of possible

    2024年01月20日
    浏览(43)
  • 【算法|动态规划No.6】leetcode63. 不同路径Ⅱ

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月16日
    浏览(49)
  • 【算法|动态规划No.17】leetcode64. 最小路径和

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月07日
    浏览(49)
  • 【算法|动态规划系列No.5】leetcode62. 不同路径

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月12日
    浏览(43)
  • 【算法|动态规划No.12】leetcode152. 乘积最大子数组

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月08日
    浏览(45)
  • 【算法|动态规划No.7】leetcode300. 最长递增子序列

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月07日
    浏览(46)
  • 【算法|动态规划No.15】leetcode1035. 不相交的线

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月06日
    浏览(44)
  • leetCode 131.分割回文串 + 动态规划 + 回溯算法 + 优化 + 图解 + 笔记

    我的往期文章: leetCode 647.回文子串 动态规划 + 优化空间 / 中心扩展法 + 双指针-CSDN博客 https://blog.csdn.net/weixin_41987016/article/details/133883091?spm=1001.2014.3001.5501 leetCode 131.分割回文串 + 回溯算法 + 图解 + 笔记-CSDN博客 https://blog.csdn.net/weixin_41987016/article/details/134700907?spm=1001.2014.3001

    2024年02月05日
    浏览(56)
  • LeetCode算法题解(动态规划)|LeetCoed62. 不同路径、LeetCode63. 不同路径 II

    题目链接:62. 不同路径 题目描述: 一个机器人位于一个  m x n   网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径? 示例 1: 示例 2:

    2024年02月05日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包