1723 - 完成所有工作的最短时间 - DFS - 剪枝 - DAG - 动态规划 - bitset

LightningBilly · 2021 年1 月 12 日 08:26

欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。

[toc]

题目描述

[1723] 完成所有工作的最短时间

力扣)

给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。

请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的工作时间是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的最大工作时间得以最小化。

返回分配方案中尽可能最小的最大工作时间。

示例 1：

输入：jobs = [3,2,3], k = 3
输出：3
解释：给每位工人分配一项工作，最大工作时间是 3 。
示例 2：

输入：jobs = [1,2,4,7,8], k = 2
输出：11
解释：按下述方式分配工作：
1 号工人：1、2、8（工作时间 = 1 + 2 + 8 = 11）
2 号工人：4、7（工作时间 = 4 + 7 = 11）
最大工作时间是 11 。

提示：

1 <= k <= jobs.length <= 12
1 <= jobs[i] <= 10^7

题目剖析&信息挖掘

此题考查的是子集生成算法和对集合状态压缩的运用，与[1681] 最小不兼容性有些类似。可以用状态压缩dp 或搜索+剪枝的算法来解决。我也有尝试过用二分查找，但还是基于搜索来实现的，最终验证复杂度过高没有通过了。

解题思路

思考

题目本质上是把一堆数字分成几个集合，然后使得集合总和最大的值最小化。

由于数字最多只有12个，完全可以用一个int32位表示一个集合。

具体可以看一下这篇，[1681] 最小不兼容性

那么集合的种类就是有1<<len(jobs)个。

题目就转化成从0到1<<len(jobs)-1 集合中选出 x (x<=k)个，这x个集合不相交，且并集刚好是1<<len(jobs)。使得集合的总和最大值最小。

方法一巧用数字表示集合+搜索+剪枝

分析

如何确保每种组合只选择一次。

从1<<len(jobs)数字中选择x个数字，与顺序无关，所以是组合。
比如 0,1,2,3 表示的是集合。
那么我们在选择时就会选出1,2,3是一种，3，2，1也是一种，但其实这2种组合是等价的。
这里我们规定选择出来是一个递增序列来确保每种组合只会被选择一次。

剪枝条件

剪枝条件可以说是搜索算法效率最核心的要素。
条件越苛刻，效率就会越高，要尽量多的去挖掘。
条件一：如果目前个人用时最大值大于等于当前最优解，直接返回。
条件二：如果任务已经分配完了，更新最优解返回。
条件三：任务未分配完，人员已经用完，直接返回。
条件四：根据贪心原理，如果人数大于等于任务数，那么就只有一种情况，大家一人分一个，计算并更新最优解返回。
条件五：每次选择的集合必须是目前任务的子集。

思路

先根据题目的数组构造出所有的集合（事先计算好集合的总用时）。
利用dfs算法，对每一层选择一个集合。
判断剪枝条件，更新最解解。

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

type M struct {
	minCost int // 存储当前最优解
	jobsNum []int // 存储集合中的任务数
	setCost []int // 存储集合用时
}

func (m *M) dfs(maxJobsNum, maxCostBefore, leftJobs, leftWorkers int) {
	// 条件一：当前最大用时大于等于最优解

	// 条件二：任务已经分配完毕

	// 条件三：任务未分配完，人员已经用完，直接返回

	// 条件四：根据贪心原理，如果人数大于等于任务数，那么就只有一种情况，大家一人分一个，计算并更新最优解返回。

	// 选择的编号要比之前的都要大。 i>leftJobs 时，i&leftJobs != i 总是成立的。
	for i:=maxJobsNum+1;i<=leftJobs ;i++  {
    // 条件五: 选择的工作集不在剩下的里面
		if i&leftJobs != i{
			continue
		}

		m.dfs(max(i, m.jobsNum[i]), max(maxCostBefore, m.setCost[i]), leftJobs-i,leftWorkers-1)
	}
}


func (m *M) GetMinCost(n, k int) int {
	m.minCost = m.setCost[len(m.setCost)-1] // 默认全给一人个做
	m.dfs(0,0, (1<<uint(n))-1, k)
	return m.minCost
}

func minimumTimeRequired(jobs []int, k int) int {

	m := &M{}
	m.setCost = getCost(jobs) // 计算所有集合用时
	m.jobsNum = getJobsNum(jobs) // 计算集合作务总数
	return m.GetMinCost(len(jobs), k)
}

注意

最优解要初始化
防止重复选择组合

知识点

bitset
DFS
搜索&剪枝

复杂度

时间复杂度：不好估，剪枝优化了
空间复杂度：O(2^n)

参考

[1681] 最小不兼容性

代码实现

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func getJobsNum(jobs []int) []int{
	cnt :=  make([]int, (1<<uint(len(jobs))))
	cnt[0] = 0
	for i:=1; i< (1<<uint(len(jobs)));i++  {
		cnt[i] = cnt[i>>1]
		if i&1>0 {cnt[i]++}
	}

	return cnt
}

func getCost(jobs []int) []int{
	cost := make([]int, (1<<uint(len(jobs))))
	for i:=0; i< (1<<uint(len(jobs)));i++  {
		cost[i] = 0
		for j:=uint(0);int(j)<len(jobs);j++ {
			if (1<<j) & i == 0{ continue}
			cost[i] += jobs[j]
		}
	}

	return cost
}

type M struct {
	minCost int // 存储当前最优解
	jobsNum []int // 存储集合中的任务数
	setCost []int // 存储集合用时
}

func (m *M) dfs(maxJobsNum, maxCostBefore, leftJobs, leftWorkers int) {
	// 条件一：当前最大用时大于等于最优解
	if maxCostBefore>= m.minCost {
		return
	}

	// 条件二：任务已经分配完毕
	if leftJobs==0 {
		m.minCost = min(maxCostBefore, m.minCost)
		return
	}

	// 条件三：任务未分配完，人员已经用完，直接返回
	if leftWorkers == 0{
		return
	}

	// 条件四：根据贪心原理，如果人数大于等于任务数，那么就只有一种情况，大家一人分一个，计算并更新最优解返回。
	if m.jobsNum[leftJobs]<=leftWorkers {
		for i:=uint(0);(1<<i)<=leftJobs;i++ {
			if (1<<i)&leftJobs != (1<<i) {continue}
			maxCostBefore = max(maxCostBefore, m.setCost[1<<i])
		}
		m.minCost = min(maxCostBefore, m.minCost)
		return
	}

	// 选择的编号要比之前的都要大。 i>leftJobs 时，i&leftJobs != i 总是成立的。
	for i:=maxJobsNum+1;i<=leftJobs ;i++  {
    // 条件五: 选择的工作集不在剩下的里面
		if i&leftJobs != i{
			continue
    }

		m.dfs(max(i, m.jobsNum[i]), max(maxCostBefore, m.setCost[i]), leftJobs-i,leftWorkers-1)
	}
}


func (m *M) GetMinCost(n, k int) int {
	m.minCost = m.setCost[len(m.setCost)-1] // 默认全给一人个做
	m.dfs(0,0, (1<<uint(n))-1, k)
	return m.minCost
}

func minimumTimeRequired(jobs []int, k int) int {

	m := &M{}
	m.setCost = getCost(jobs) // 计算所有集合用时
	m.jobsNum = getJobsNum(jobs) // 计算集合作务总数
	return m.GetMinCost(len(jobs), k)
}
/*
func main() {
	fmt.Println(minimumTimeRequired([]int{3,2,3},  3))
	fmt.Println(minimumTimeRequired([]int{1,2,4,7,8},  2))
	fmt.Println(minimumTimeRequired([]int{12343,2223,4222,721,82323,3923,222,1122,34563,29309,222,33445},  10))
	fmt.Println(minimumTimeRequired([]int{6518448,8819833,7991995,7454298,2087579,380625,4031400,2905811,4901241,8480231,7750692,3544254},  4))
}
*/

方法二巧用数字表示集合+DAG+动态规划

分析

设目前任务集合为s, 人数为n。

dp[n][s] 表示 n个人，任务集合为s的情况下最大个人用时。

对于任务数量为x，人数为n，dp[n][(1<<x)-1] 就是答案。

初始状态：

dp[i\][0] = 0没有任务都是0
dp[0][j] = INTMAX32 (j>0) 0人，还有任务，不可能完成，这里给一个极大值。

转移方程：

每次我们尝试为当前（第i个）工人选择一个j的子集k(k&j == k)，作为他的工作。
那么最终个人最大用时就是 max(cost[k], dp[i-1\][j-k])
dp[i\][j] = min(max(cost[k], dp[i-1\][j-k])) (k&j==k)

以上是大致的思路，实际代码中有利用贪心原理进行一些常数优化。

思路

先根据题目的数组构造出所有的集合（事先计算好集合的总用时和任务数）。
初始化dp
利用递推计算dp
返回dp[n][1<<len(jobs)-1]


func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}


func minimumTimeRequired(jobs []int, k int) int {
	setCost := getCost(jobs) // 计算集合用时
	jobCnt := getJobsNum(jobs) // 计算集合中的任务
	dp := initDp(len(jobs), k+1) // 申请内存
  // 初始化
	for i, _ := range dp[0] {
		
	}
	for i:=1;i<=k;i++ {
		dp[i][0]=0 // 没有任务
		for j:=1;j<len(dp[i]);j++ {
			// 人比任务多，直接复制少一人的答案。

			// 默认让一个人做
			for selectJobs := 0;selectJobs<j;selectJobs++ {
				// 选择的任务不是J的子集。
			}
		}
	}
	//showDp(dp)

	return dp[k][(1<<uint(len(jobs)))-1]
}

注意

dp要初始化
选择的是当前集合的子集

知识点

bitset
DAG
动态规划

复杂度

时间复杂度：O(2^n)
空间复杂度：O(2^n)

参考

利用DAG模型求解动态规划问题

代码实现


func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func getJobsNum(jobs []int) []int{
	cnt :=  make([]int, (1<<uint(len(jobs))))
	cnt[0] = 0
	for i:=1; i< (1<<uint(len(jobs)));i++  {
		cnt[i] = cnt[i>>1]
		if i&1>0 {cnt[i]++}
	}

	return cnt
}

func getCost(jobs []int) []int{
	cost := make([]int, (1<<uint(len(jobs))))
	for i:=0; i< (1<<uint(len(jobs)));i++  {
		cost[i] = 0
		for j:=uint(0);int(j)<len(jobs);j++ {
			if (1<<j) & i == 0{ continue}
			cost[i] += jobs[j]
		}
	}

	return cost
}

func initDp(n, k int) [][]int{
	dp := make([][]int, k)
	for i, _ := range dp {
		dp[i] = make([]int, 1<<uint(n))
	}
	return dp
}

func showDp(dp [][]int) {
	//fmt.Printf("%03b", 2)
	fmt.Print("  ")
	for i:=0;i<len(dp[0]);i++ {
		fmt.Printf("%03b ", i)
	}
	fmt.Println()
	for i, v := range dp {
		fmt.Printf("%d", i)

		for _, x := range v {
			fmt.Printf("%4d", x)
		}
		fmt.Println()
	}

	fmt.Println()
}

func minimumTimeRequired(jobs []int, k int) int {
	setCost := getCost(jobs)
	jobCnt := getJobsNum(jobs)
	dp := initDp(len(jobs), k+1)
	for i, _ := range dp[0] {
		if i==0 { // 没有任务0时完成
			dp[0][0]=0
			continue
		}
		// 0人多任务， 无法完成
		dp[0][i] = math.MaxInt32
	}
	for i:=1;i<=k;i++ {
		dp[i][0]=0 // 没有任务
		for j:=1;j<len(dp[i]);j++ {
			if i>jobCnt[j] { // 人比任务多，直接复制少一人的答案。
				dp[i][j] = dp[i-1][j]
				continue
			}

			dp[i][j] = setCost[j] // 默认让一个人做
			for selectJobs := 0;selectJobs<j;selectJobs++ {
				if selectJobs&j != selectJobs {continue}// 选择的任务不是J的子集。
				dp[i][j] = min(dp[i][j], max(setCost[selectJobs], dp[i-1][j-selectJobs]))
			}
		}
	}
	//showDp(dp)

	return dp[k][(1<<uint(len(jobs)))-1]
}

1723 - 完成所有工作的最短时间 - DFS - 剪枝 - DAG - 动态规划 - bitset

题目描述

题目剖析&信息挖掘

解题思路

方法一 巧用数字表示集合+搜索+剪枝

分析

思路

注意

知识点

复杂度

参考

代码实现

方法二 巧用数字表示集合+DAG+动态规划

分析

思路

注意

知识点

复杂度

参考

代码实现

相关题目

方法一巧用数字表示集合+搜索+剪枝

方法二巧用数字表示集合+DAG+动态规划