https://leetcode.com/problems/fair-distribution-of-cookies/description/
2305. Fair Distribution of Cookies
給你一個陣列 cookies[]，cookies[i] 表示每個袋子裡的餅乾數量，袋子裡的餅乾
不可以拆分，我們要把餅乾分給 k 個小孩，每個小孩需要拿至少一袋，不公平度
被定義成每個小孩的餅乾數量中取最大，求出最小的不公平度。
Example 1:
Input: cookies = [8,15,10,20,8], k = 2
Output: 31
Explanation: One optimal distribution is [8,15,8] and [10,20]
- The 1st child receives [8,15,8] which has a total of 8 + 15 + 8 = 31
cookies.
- The 2nd child receives [10,20] which has a total of 10 + 20 = 30 cookies.
The unfairness of the distribution is max(31,30) = 31.
It can be shown that there is no distribution with an unfairness less than 31.
Example 2:
Input: cookies = [6,1,3,2,2,4,1,2], k = 3
Output: 7
Explanation: One optimal distribution is [6,1], [3,2,2], and [4,1,2]
- The 1st child receives [6,1] which has a total of 6 + 1 = 7 cookies.
- The 2nd child receives [3,2,2] which has a total of 3 + 2 + 2 = 7 cookies.
- The 3rd child receives [4,1,2] which has a total of 4 + 1 + 2 = 7 cookies.
The unfairness of the distribution is max(7,7,7) = 7.
It can be shown that there is no distribution with an unfairness less than 7.
思路：
1.先從窮舉開始想，餅乾有 n 個分給 k 個小孩，每個餅乾有 k 種分法，所以共有
k^n 種分法，題目的 n 和 k 最多為 8 ，還可以接受用 DFS 窮舉。
2.假定餅乾結構為 [3, 2, 1] 且 k = 2 ，cnt[] 定義為每個小孩的餅乾數量，則所有
的分配結果如下：
左:該小孩拿餅乾
右:該小孩不拿餅乾
cnt = [0,0] _______________
/ \
餅乾一 [3,0] [0,3]
/ \ / \
餅乾二 [5,0] [3,2] [2,3] [0,5]
/ \ / \ / \ /\ / \ / \
餅乾三 [6,0] [5,1][4,2][3,3] [3,3][2,4] [1,5][0,6]
將最後一個餅乾分配完之後的 cnt 取最大元素後，再把每個結果最大元素取最小值
就是答案了（3, 3）
3.觀察上樹我們可以發現，右邊的回溯樹就是左邊的反方向（只有順序不同），當我們
發第一個餅乾的時候無論是給哪一個小孩，產生的樹都會是一樣的結構，只有餅乾順序
不同不會產生比先前更優的解，所以我們可以檢查當前面的小孩沒有拿到餅乾時，他後
面長出來的樹就可以不用看了。
Java Code：
-------------------------------------------------------------
class Solution {
private int res;
public int distributeCookies(int[] cookies, int k) {
res = Integer.MAX_VALUE;
backTracking(cookies, new int[k], 0);
return res;
}
private void backTracking(int[] cookies, int[] cnt, int idx) {
if (idx == cookies.length) {
res = Math.min(res, getMax(cnt));
return;
}
for (int i = 0; i < cnt.length; i++) {
cnt[i] += cookies[idx];
backTracking(cookies, cnt, idx + 1);
cnt[i] -= cookies[idx];
if (cnt[i] == 0) break;
}
}
private int getMax(int[] cookies) {
int max = 0;
for (int cookie : cookies) {
max = Math.max(max, cookie);
}
return max;
}
}
-------------------------------------------------------------
--
https://i.imgur.com/YPBHGGE.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1688236092.A.B8A.html