|
你被安排了 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
Related Topics 位运算 数组 动态规划 回溯 状态压缩
任务序号从1开始。
- 状态表示
f[mask]表示当选择任务的状态是mask时，最少需要的工作时间段。其中mask是一个长度为n的二进制表示，mask从低到高的第i位表示第i个任务已经完成，0表示第i个任务未完成。相当于mask为1的位构成的任务集合。
如例1：
f[1] = f[001] <=> {1}
f[2] = f[010] <=> {2}
f[3] = f[011] <=> {1,2}
f[4] = f[100] <=> {3}
f[5] = f[101] <=> {1,3}
f[6] = f[110] <=> {2,3}
f[7] = f[111] <=> {1,2,3}
- 状态转移
在进行状态转移时，先枚举在最后一个工作时间段完成了哪些任务，这些任务对应的状态subset一定是mask的一个子集。
这里"子集"的含义为：subset是mask的一个子集，当且仅当subset中任意的1在mask中的对应位置均为1.
状态转移方程为：
f[mask] = min(subset∈mask) {f[mask\subset] + 1}
mask/subset 表示将subset中的所有1从mask中移除后的二进制表示，可以使用按位异或运算求出。
注意：subset中包含的任务的工作时间总和不能大于sessionTime.因此在动态规划之前进行预处理，枚举[1, 2^n)范围的二进制表示mask，计算如果mask表示的任务所需要的工作时间之和小于等于sessionTime，那么将valid[mask]置为True，否则置为False.
如例1：
valid[000] = 0 False
valid[001] = 1 True
valid[010] = 2 True
valid[011] = 1 + 2 = 3 True
valid[100] = 3 True
valid[101] = 1 + 3 False
valid[111] = 1 + 2 + 3 True
3.枚举子集subset的技巧
subset = mask
while subset != 0:
# subset 是 mask 的一个子集，可以用其进行状态转移
...
# 使用按位与运算在O(1)时间快速得到夏邑（即更小的）mask
subset = (subset - 1) & mask
code:
class Solution:
def minSessions(self, tasks, sessionTime: int) -> int:
n = len(tasks)
valid = [False] * (1 << n) # 用于存储第 i 种状态是否可以在一个时间段内完成
for mask in range(1, 1 << n):
needtime = 0
for i in range(n):
if mask & (1 << i): # 判断第i位是否是1
needtime += tasks[i]
if needtime <= sessionTime:
valid[mask] = True
# print(valid)
# 状压dp
f = [float("inf")] * (1 << n)
f[0] = 0
for mask in range(1, 1 << n):
subset = mask
while subset != 0:
if valid[subset]:
f[mask] = min(f[mask], f[mask ^ subset] + 1)
subset = (subset - 1) & mask
return f[(1 << n) - 1]
s = Solution()
print(s.minSessions(tasks = [1,2,3], sessionTime = 3))
参考：https://leetcode-cn.com/problems/minimum-number-of-work-sessions-to-finish-the-tasks/solution/wan-cheng-ren-wu-de-zui-shao-gong-zuo-sh-tl0p/
|