状态压缩动态规划

leetcode 状态压缩动态规划

题目描述：

5639. 完成所有工作的最短时间

给你一个整数数组 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] <= 107

分析：

1 状态压缩：

\(jobs [a_1, a_2, ..., a_n]\) 假设长度为n，那么从jobs中取出元素的情况有\(2^n\) 种(每个\(a_i\)取或者不取)，每种状态都可以可以用一个n位的二进制数\(i\)表示 \(i \in\)[0, \(2^n-1\)]，

准确说\(i\)表示的是一个集合，该集合包含jobs中元素若干，比如对于jobs = [3,2,3]，使用3（二进制就是011）表示选取了3，2两个元素。使用7（二进制111）表示选取了3，2，3元素；使用5（二进制101）表示选取了3，3两个元素。

2 动态规划

\(tot[i]\) 表示的是集合\(i\)中所含工作时间的总和，那么设\(i\)中某个元素在jobs中的下标为\(j\)，\(i - (1<<j)\) 表示从集合i中去掉了元素j，则可以得到

\(tot[i] = tot[i - (1<<j)] + jobs[j]\)

使用\(dp[j][i]\)表示：前\(j\)个工人完成工作子集\(i\)所用的最大时间的最小值

状态转移方程为：\(dp[j][i] = min_{s \sube i} (max(dp[j-1][i-s], tot[s]))\)

\(dp[j-1][i-s]\)表示前\(j-1\)个工人，完成工作子集\(i-s\)所用的最大时间的最小值，\(tot[s]\)表示的就是第\(j\)个工人完成工作子集\(s\)所用的时间

AC代码：

class Solution {
public:
    int minimumTimeRequired(vector<int>& jobs, int k) {
		int n = jobs.size();
		vector<int> tot(1<<n, 0); //创建一个2^n大小的tot数组，每个元素表示一个集合 
									// tot[i] 表示集合i的总工作时间
		// 集合0表示所有工作都不选，这种不用考虑 
		for(int i = 1; i < (1<<n); ++i) {
			for (int j = 0; j < n; ++j) {
				
				if((i & (1<<j)) == 0) continue; // 如果集合i中没有j这个元素 
				
				int rest = i - (1<<j);  // rest相当于把i的第j位清零
                
				tot[i] = tot[rest] + jobs[j]; //把jobs[j]的时间加入到集合中 
				break;//  
			}
		} 
		
		// 
		vector<vector<int>> dp(k, vector<int>(1<<n, -1));
		//初始化
		for (int i = 0; i < (1<<n); ++i) {
			dp[0][i] = tot[i]; //只有一个人做集合i，那么就是所有工作 
		}
		for (int i = 0; i < k; i++) {
            dp[i][0] = 0;  //集合0中有0个工作，
        }

		for(int j = 1; j < k; ++j) {
			for(int i = 1; i < (1<<n); ++i) {
				int min_val = INT_MAX;
				for(int s = i; s; s = (s-1) & i) {
                    int left = i - s;
					int val = max(dp[j-1][left], tot[s]);
					min_val = min(min_val, val);
				}
				dp[j][i] = min_val;
			}
		} 
        return dp[k-1][(1<<n)-1];
    }
};

参考题解：

https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs/solution/zhuang-ya-dp-jing-dian-tao-lu-xin-shou-j-3w7r/

状态压缩动态规划

原文：https://www.cnblogs.com/VanHa0101/p/14259665.html