本文涉及知识点

C++动态规划
位运算、状态压缩、枚举子集汇总

LeetCode1986. 完成任务的最少工作时间段

你被安排了 n 个任务。任务需要花费的时间用长度为 n 的整数数组 tasks 表示，第 i 个任务需要花费 tasks[i] 小时完成。一个 工作时间段 中，你可以 至多 连续工作 sessionTime 个小时，然后休息一会儿。
你需要按照如下条件完成给定任务：
如果你在某一个时间段开始一个任务，你需要在 同一个 时间段完成它。
完成一个任务后，你可以 立马 开始一个新的任务。
你可以按 任意顺序 完成任务。
给你 tasks 和 sessionTime ，请你按照上述要求，返回完成所有任务所需要的 最少 数目的 工作时间段 。
测试数据保证 sessionTime 大于等于 tasks[i] 中的 最大值 。
示例 1：

输入：tasks = [1,2,3], sessionTime = 3
输出：2
解释：你可以在两个工作时间段内完成所有任务。

• 第一个工作时间段：完成第一和第二个任务，花费 1 + 2 = 3 小时。
• 第二个工作时间段：完成第三个任务，花费 3 小时。
  示例 2：

输入：tasks = [3,1,3,1,1], sessionTime = 8
输出：2
解释：你可以在两个工作时间段内完成所有任务。

• 第一个工作时间段：完成除了最后一个任务以外的所有任务，花费 3 + 1 + 3 + 1 = 8 小时。
• 第二个工作时间段，完成最后一个任务，花费 1 小时。
  示例 3：

输入：tasks = [1,2,3,4,5], sessionTime = 15
输出：1
解释：你可以在一个工作时间段以内完成所有任务。
提示：
n == tasks.length
1 <= n <= 14
1 <= tasks[i] <= 10
max(tasks[i]) <= sessionTime <= 15

动态规划 子集状压 位运算

动态规划的状态表示

j表示任务完成情况，(1<<k)&j表示第k个任务是否完成。
vSum[j]记录完成任务j所有需要的时间。
一，初始vSum[2^x]。
二，j从2到大枚举j，vSum[j] = vSum[j&-j]+vSum[j&(j-1)]
dp[j] 表示完成任务j需要的天数。

动态规划的填报顺序

j从小到大

动态规划的转移方程

每个状态j：
如果vSum[j] <= 一天的最大工作量，则dp[j]=1。否则：
枚举j 的 非空不等于j的子集sub:
MinSelf(dp[j],dp[sub]+dp[j-sub])

动态规划的初始值

dp[0]为0，其它全部为INT_MAX/2。

动态规划的返回值

dp.back()

代码

核心代码

class Solution {
		public:
			int minSessions(vector<int>& tasks, int sessionTime) {
				const int N = tasks.size();
				const int MC = 1 << N;
				vector<int> sum(MC);
				for (int i = 0; i < N; i++) {
					sum[1 << i] = tasks[i];
				}
				for (int i = 2; i < MC; i++) {
					sum[i] = sum[i & (i - 1)] + sum[i & -i];
				}
				vector<int> dp(MC,INT_MAX/2);
				dp[0] = 0;
				for (int i = 1; i < MC; i++) {
					if (sum[i] <= sessionTime) { dp[i] = 1; continue; }
					for (int sub = i; sub; sub = (sub - 1) & i) {
						dp[i] = min(dp[i], dp[sub] + dp[i-sub]);
					}					
				}
				return dp.back();
			}
		};

单元测试

vector<int> tasks;
		int sessionTime;
		TEST_METHOD(TestMethod11)
		{
			tasks = { 1, 2, 3 }, sessionTime = 3;
			auto res = Solution().minSessions(tasks, sessionTime);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			tasks = { 3,1,3,1,1 }, sessionTime = 8;
			auto res = Solution().minSessions(tasks, sessionTime);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod13)
		{
			tasks = { 1,2,3,4,5 }, sessionTime = 15;
			auto res = Solution().minSessions(tasks, sessionTime);
			AssertEx(1, res);
		}