golang刷letcode：公平分发饼干
golang刷letcode：公平分发饼干
给你一个整数数组 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] <= 105
2 <= k <= cookies.length
解题思路
1，本题是背包问题的变形，只不过是分配给每个孩子的事集合的子集
2，假设数组长度为n，那么数组的子集个数为2^n
3， 可以于处理所有子集合的元素和 ：计算位置i以前的所有枚举集合的元素和；即2^（i+1）个枚举集合的和；对于每一个子集可以通过固定位置i，枚举比i小的所有位置，通过位运算来实现。
4，定义状态转移方程 f[i][j], 前i个孩子，分配的枚举集合j，得到的不公平程度最小值，其中有两层含义：求每一种分配的不公平程度（拆分成不同集合的时候，每个孩子分配的饼干和最大值），求所有不公平程度的最小值。
5，对于前i个孩子，在分配元素组成的集合的子集时候，假设第i个孩子分配了集合s；此时的不公平程度为max(f[i-1][j^s],sum[s]), 即不包含s的剩余集合分配给前i-1个元素的不公平程度最小值和s集合的和，两者取小者；其中s的枚举范围为0到j
6，i个孩子分配元素集合j的最小不公平程度为：f[i][j]=min(f[i][j],max(f[i-1][j^s],sum[s]));其中j的枚举范围是0到m；
7，我们的答案就是分配给k个孩子，集合枚举情况m的最小值，f[k-1][m-1]
8，初始条件，f[0][j]=sum[j];其中j取值是0到m;把集合只分配给一个孩子，最小不公平程度就是集合的元素和；f[i][j]=sum[j]为不公平程度的最大值,假设所有元素都分配给孩子i，不公平程度不会比这个更大
9，由于i依赖i-1所以是递增；由于j是从更大的集合取差集，所以j递减;
10，枚举集合j中的所有子集合可以使用位运算技巧，(s-1)&j
代码实现：
func distributeCookies(cookies []int, k int) int {
m := 1 << len(cookies)
sum := make([]int, m)
for i, v := range cookies {
for mask, bit := 0, 1<<i; mask < bit; mask++ {
sum[bit|mask] = sum[mask] + v
}
}
f:=make([][]int,k)
for i:=0;i<k;i++{
f[i]=make([]int,m)
}
f[0]=sum
for i:=1;i<k;i++{
for j:=m-1;j>0;j--{
f[i][j]=sum[j]
for s:=j;s>0;s=(s-1)&j{
f[i][j]=min(f[i][j],max(f[i-1][j^s],sum[s]))
}
}
}
return f[k-1][m-1]
}
func min(a, b int) int { if a > b { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }由于每个i只依赖i-1，所以可以进行优化，压缩掉一维
func distributeCookies(cookies []int, k int) int {
m := 1 << len(cookies)
sum := make([]int, m)
for i, v := range cookies {
for mask, bit := 0, 1<<i; mask < bit; mask++ {
sum[bit|mask] = sum[mask] + v
}
}
f := append([]int{}, sum...)
for i := 1; i < k; i++ {
for j := m - 1; j > 0; j-- {
for s := j; s > 0; s = (s - 1) & j {
f[j] = min(f[j], max(f[j^s], sum[s]))
}
}
}
return f[m-1]
}本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与?腾讯云自媒体分享计划? ，欢迎热爱写作的你一起参与！