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]
}

复制