golang刷leetcode：公平分發(fā)餅干

給你一個(gè)整數(shù)數(shù)組 cookies ，其中 cookies[i] 表示在第 i 個(gè)零食包中的餅干數(shù)量。另給你一個(gè)整數(shù) k 表示等待分發(fā)零食包的孩子數(shù)量，所有 零食包都需要分發(fā)。在同一個(gè)零食包中的所有餅干都必須分發(fā)給同一個(gè)孩子，不能分開。

分發(fā)的 不公平程度 定義為單個(gè)孩子在分發(fā)過程中能夠獲得餅干的最大總數(shù)。

返回所有分發(fā)的最小不公平程度。

示例 1：

輸入：cookies = [8,15,10,20,8], k = 2

輸出：31

解釋：一種最優(yōu)方案是 [8,15,8] 和 [10,20] 。

- 第 1 個(gè)孩子分到 [8,15,8] ，總計(jì) 8 + 15 + 8 = 31 塊餅干。

- 第 2 個(gè)孩子分到 [10,20] ，總計(jì) 10 + 20 = 30 塊餅干。

分發(fā)的不公平程度為 max(31,30) = 31 。

可以證明不存在不公平程度小于 31 的分發(fā)方案。

示例 2：

輸入：cookies = [6,1,3,2,2,4,1,2], k = 3

輸出：7

解釋：一種最優(yōu)方案是 [6,1]、[3,2,2] 和 [4,1,2] 。

- 第 1 個(gè)孩子分到 [6,1] ，總計(jì) 6 + 1 = 7 塊餅干。 

- 第 2 個(gè)孩子分到 [3,2,2] ，總計(jì) 3 + 2 + 2 = 7 塊餅干。

- 第 3 個(gè)孩子分到 [4,1,2] ，總計(jì) 4 + 1 + 2 = 7 塊餅干。

分發(fā)的不公平程度為 max(7,7,7) = 7 。

可以證明不存在不公平程度小于 7 的分發(fā)方案。

提示：

2 <= cookies.length <= 8

1 <= cookies[i] <= 105

2 <= k <= cookies.length

解題思路

1，本題是背包問題的變形，只不過是分配給每個(gè)孩子的事集合的子集

2，假設(shè)數(shù)組長(zhǎng)度為n，那么數(shù)組的子集個(gè)數(shù)為2^n

3，  可以于處理所有子集合的元素和 ：計(jì)算位置i以前的所有枚舉集合的元素和；即2^（i+1）個(gè)枚舉集合的和；對(duì)于每一個(gè)子集可以通過固定位置i，枚舉比i小的所有位置，通過位運(yùn)算來實(shí)現(xiàn)。

4，定義狀態(tài)轉(zhuǎn)移方程 f[i][j],  前i個(gè)孩子，分配的枚舉集合j，得到的不公平程度最小值，其中有兩層含義：求每一種分配的不公平程度（拆分成不同集合的時(shí)候，每個(gè)孩子分配的餅干和最大值），求所有不公平程度的最小值。

5，對(duì)于前i個(gè)孩子，在分配元素組成的集合的子集時(shí)候，假設(shè)第i個(gè)孩子分配了集合s；此時(shí)的不公平程度為max(f[i-1][j^s],sum[s]), 即不包含s的剩余集合分配給前i-1個(gè)元素的不公平程度最小值和s集合的和，兩者取小者；其中s的枚舉范圍為0到j(luò)

6，i個(gè)孩子分配元素集合j的最小不公平程度為：f[i][j]=min(f[i][j],max(f[i-1][j^s],sum[s]));其中j的枚舉范圍是0到m；

7，我們的答案就是分配給k個(gè)孩子，集合枚舉情況m的最小值，f[k-1][m-1]

8，初始條件，f[0][j]=sum[j];其中j取值是0到m;把集合只分配給一個(gè)孩子，最小不公平程度就是集合的元素和；f[i][j]=sum[j]為不公平程度的最大值,假設(shè)所有元素都分配給孩子i，不公平程度不會(huì)比這個(gè)更大

9，由于i依賴i-1所以是遞增；由于j是從更大的集合取差集，所以j遞減;

 10，枚舉集合j中的所有子集合可以使用位運(yùn)算技巧，(s-1)&j

代碼實(shí)現(xiàn)：

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 }

由于每個(gè)i只依賴i-1，所以可以進(jìn)行優(yōu)化，壓縮掉一維

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：我能贏嗎