https://leetcode.com/problems/fair-distribution-of-cookies/
由於這一題數據量不大，因此其中一個方法就是暴力解，直接遍歷所有的可能性。
用到方法也是非常經典的 backtracking。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| int distributeCookies(vector<int>& cookies, int k) {
int n = cookies.size();
if (n == k){
return *max_element(begin(cookies), end(cookies));
}
vector<int> distribution(k, 0);
int ans = reduce(begin(cookies), end(cookies));
back_track(cookies, distribution, 0, ans);
return ans;
}
void back_track(vector<int>& cookies, vector<int> &distribution, int cur, int &ans){
int n = cookies.size();
if (cur >= n){
ans = min(ans, *max_element(begin(distribution), end(distribution)));
return;
}
int k = distribution.size();
for (int i = 0; i < k; i++){
distribution[i] += cookies[cur];
back_track(cookies, distribution, cur + 1, ans);
distribution[i] -= cookies[cur];
}
return;
}
|
time complexity: $O(k^n)$
space complextiy: $O(k)$
where n = cookies.length
另一個方法是 dynamic programming。
由於小朋友是同質的，也就是全部餅乾分給 1 號小朋友或是全部餅乾分給 2 號小朋友，其實並沒有差異，因此可以用 dynamic programming 來記錄這種重複的問題。
用二進位的數字 mask 來記錄餅乾的使用情況，i 來記錄還剩下幾位小朋友可以分餅乾。
例如：dp[i = 3][mask = 5] = dp[3][$101_2$] 記錄的就是「在剩下 3 個小朋友，並且第 0，2 塊餅乾可以被分的情況下，拿最多餅乾的小朋友分了是多少餅乾（unfairness）？」。
此時有 $2^2$ 種分法，也就是
- 第 0，2 號餅乾給其中一位小朋友，此時子問題是 dp[2][$000_2$]
- 第 0 號餅乾給其中一位小朋友，此時子問題是 dp[2][$100_2$]
- 第 2 號餅乾給其中一位小朋友，此時子問題是 dp[2][$001_2$]
- 沒有餅乾給其中一位小朋友，此時子問題是 dp[2][$000_2$]
只要在這些情況裡面找最小的 unfairness 就好。至於這個小朋友是誰並不重要，因為小朋友是同質的。
找 unfairness 的方法也很簡單。
例如 2 號分法中，unfairness 會是 max(第 0 號餅乾的和, dp[2][$100_2$])，再跟現有的 unfairness 取較小的即可。
同時使用 sum[mask] 來記錄的就是 mask 中所有餅乾的和，這樣計算子問題的時候也會比較快。
例如： sum[$101_2$] = 第 0，2 號餅乾的和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| int distributeCookies(vector<int>& cookies, int k) {
int n = cookies.size();
vector<int> sum((1 << n), 0);
for (int i = 1; i < (1 << n); i++){
for (int j = 0; j < n; j++){
if ((i & (1 << j)) != 0){
sum[i] += cookies[j];
}
}
}
vector<vector<int>> dp(k + 1, vector<int> ((1 << n), INT_MAX));
dp[0][0] = 0;
for (int i = 1; i <= k; i++){
for (int mask = 1; mask < (1 << n); mask++){
// submask means one child get "submask" this much of cookies, which is sum[submask]
for (int submask = 0; submask <= mask; submask++){
if ((submask | mask) == mask){ // check submask is valid or not
dp[i][mask] = min(dp[i][mask], max(sum[submask], dp[i - 1][mask ^ submask]));
}
}
}
}
return dp[k][(1 << n) - 1];
}
|
time complexity: $O(2^n \times n + k \times 2^n \times 2^n)$
space complextiy: $O(k \times 2^n)$
where n = cookies.length
但是其實還可以再優化一下，因為在遍歷 submask 的時候，其實遍歷了很多不符合條件的 submask。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| int distributeCookies(vector<int>& cookies, int k) {
int n = cookies.size();
vector<int> sum((1 << n), 0);
for (int i = 1; i < (1 << n); i++){
for (int j = 0; j < n; j++){
if ((i & (1 << j)) != 0){
sum[i] += cookies[j];
}
}
}
vector<vector<int>> dp(k + 1, vector<int> ((1 << n), INT_MAX));
dp[0][0] = 0;
for (int i = 1; i <= k; i++){
for (int mask = 1; mask < (1 << n); mask++){
for (int submask = mask; submask != 0; submask = (submask - 1) & mask){ // 改了這裡
dp[i][mask] = min(dp[i][mask], max(sum[submask], dp[i - 1][mask ^ submask]));
}
}
}
return dp[k][(1 << n) - 1];
}
|
上面這段 code 我覺得最精華的部分在於 submask = (submask - 1) & mask。這樣只會遍歷所有的子問題，而不會遍歷到其他不相干的狀況。
接下來研究一下下面這段 code 的複雜度。
1
2
3
4
5
| for (int mask = 1; mask < (1 << n); mask++){
for (int submask = mask; submask != 0; submask = (submask - 1) & mask){
dp[i][mask] = min(dp[i][mask], max(sum[submask], dp[i - 1][mask ^ submask]));
}
}
|
mask 如果有 k 個 1 bit，那麼會有 $2^k$ 個 submask。
而 mask 從 1 遍歷到 (1 « n)，總共會有
$\binom{n}{1}$ 個 mask 有 1 個 1 bit
$\binom{n}{2}$ 個 mask 有 2 個 1 bit
…
$\binom{n}{n}$ 個 mask 有 n 個 1 bit
所以複雜度會是
$\sum_{k = 1}^n \binom{n}{k} \times 2^k$，而這個剛剛好就是 $(1+2)^n$
的展開式。也就是說，這段 code 的複雜度就是 $O(3^n)$。
最後整體的複雜度就是
time complexity: $O(2^n \times n + k \times 3^n)$
space complextiy: $O(k \times 2^n)$
where n = cookies.length