本文涉及知识点

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

LeetCode2305. 公平分发饼干

给你一个整数数组 cookies ，其中 cookies[i] 表示在第 i 个零食包中的饼干数量。另给你一个整数 k 表示等待分发零食包的孩子数量，所有 零食包都需要分发。在同一个零食包中的所有饼干都必须分发给同一个孩子，不能分开。
分发的 不公平程度 定义为单个孩子在分发过程中能够获得饼干的最大总数。
返回所有分发的最小不公平程度。
示例 1：
输入：cookies = [8,15,10,20,8], k = 2
输出：31
解释：一种最优方案是 [8,15,8] 和 [10,20] 。

• 第 1 个孩子分到 [8,15,8] ，总计 8 + 15 + 8 = 31 块饼干。
• 第 2 个孩子分到 [10,20] ，总计 10 + 20 = 30 块饼干。
  分发的不公平程度为 max(31,30) = 31 。
  可以证明不存在不公平程度小于 31 的分发方案。
  示例 2：
  输入：cookies = [6,1,3,2,2,4,1,2], k = 3
  输出：7
  解释：一种最优方案是 [6,1]、[3,2,2] 和 [4,1,2] 。
• 第 1 个孩子分到 [6,1] ，总计 6 + 1 = 7 块饼干。
• 第 2 个孩子分到 [3,2,2] ，总计 3 + 2 + 2 = 7 块饼干。
• 第 3 个孩子分到 [4,1,2] ，总计 4 + 1 + 2 = 7 块饼干。
  分发的不公平程度为 max(7,7,7) = 7 。
  可以证明不存在不公平程度小于 7 的分发方案。
  提示：
  2 <= cookies.length <= 8
  1 <= cookies[i] <= 10⁵
  2 <= k <= cookies.length

动态规划 子集状压 位运算

动态规划的状态表示

dp[i][j]记录不公平度。 表示前i个小孩已经分配完毕，j表示饼干分配状态，(1<<k)&j 表示第k块饼干已经分配完毕。
vSum[j]记录对应的状态的饼干总数。
先初始化vSum[0] vSum[1] vSum[2] vSum[4] KaTeX parse error: Undefined control sequence: \cdost at position 1: \̲c̲d̲o̲s̲t̲ vSum[2^x]
然后从小到大枚举j vSum[j] = vSum[j&(-j)] + vSum[j&(j-1)]
空间复杂度：O(k2ⁿ) n是饼干的袋数。

动态规格的填表顺序

枚举前置状态，i = 0 to k-1 , 枚举剩余饼干分给当前小孩。

动态规划的转移方程

当前小孩没有分配饼干：
dp[i+1] = dp[i]
通过子集枚举所有分配饼干的方案：
remian = ( 1 << n )&j
for(cur = remian ;remian; cur = (cur-1)&remian)
MinSelf(dp[i+1][cur],max(dp[i][j]+vSum[cur]）
单个小孩时间复杂度；O(3ⁿ)
时间复杂度：O(k3ⁿ)

动态规划的初始值

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

动态规划的返回值

dp.back().back()

代码

核心代码

class Solution {
		public:
			int distributeCookies(vector<int>& cookies, int k) {
				const int N = cookies.size();
				const int iMaskCount = 1 << N;
				vector<int> vSum(iMaskCount);
				for (int i = 0; i < N; i++) {
					vSum[1 << i] = cookies[i];
				}
				for (int i = 2; i < iMaskCount; i++) {
					vSum[i] = vSum[i & (i - 1)] + vSum[i & -i];
				}
				vector<vector<int>> dp(k + 1, vector<int>(iMaskCount,INT_MAX/2));
				dp[0][0] = 0;
				for (int i = 0; i < k; i++) {
					dp[i + 1] = dp[i];
					for (int j = 0; j < iMaskCount; j++) {
						const int remain = j ^ (iMaskCount - 1);
						for (int sub = remain; sub; sub = (sub - 1) & remain) {
							dp[i + 1][j | sub] = min(dp[i + 1][j | sub], max(dp[i][j], vSum[sub]));
						}
					}
				}
				return dp.back().back();
			}
		};

单元测试

vector<int> cookies;
		int k;
		TEST_METHOD(TestMethod11)
		{
			cookies = { 8, 15, 10, 20, 8 }, k = 2;
			auto res = Solution().distributeCookies(cookies, k);
			AssertEx(31, res);
		}
		TEST_METHOD(TestMethod12)
		{
			cookies = { 6,1,3,2,2,4,1,2 }, k = 3;
			auto res = Solution().distributeCookies(cookies, k);
			AssertEx(7, res);
		}