Fair Distribution of Cookies
Problem
Distribute cookie bags to k children to minimise the maximum total any child receives. Each bag goes to exactly one child.
cookies = [8, 15, 10, 20, 8], k = 231def distribute_cookies(cookies, k):
bags = [0] * k
best = [float('inf')]
def dfs(i):
if i == len(cookies):
best[0] = min(best[0], max(bags))
return
for j in range(k):
if bags[j] + cookies[i] >= best[0]:
continue
bags[j] += cookies[i]
dfs(i + 1)
bags[j] -= cookies[i]
if bags[j] == 0:
break
dfs(0)
return best[0]function distributeCookies(cookies, k) {
const bags = new Array(k).fill(0);
let best = Infinity;
function dfs(i) {
if (i === cookies.length) {
best = Math.min(best, Math.max(...bags));
return;
}
for (let j = 0; j < k; j++) {
if (bags[j] + cookies[i] >= best) continue;
bags[j] += cookies[i];
dfs(i + 1);
bags[j] -= cookies[i];
if (bags[j] === 0) break;
}
}
dfs(0);
return best;
}class Solution {
int best;
public int distributeCookies(int[] cookies, int k) {
int[] bags = new int[k];
best = Integer.MAX_VALUE;
dfs(cookies, bags, 0);
return best;
}
void dfs(int[] cookies, int[] bags, int i) {
if (i == cookies.length) {
int m = 0;
for (int b : bags) m = Math.max(m, b);
best = Math.min(best, m);
return;
}
for (int j = 0; j < bags.length; j++) {
if (bags[j] + cookies[i] >= best) continue;
bags[j] += cookies[i];
dfs(cookies, bags, i + 1);
bags[j] -= cookies[i];
if (bags[j] == 0) break;
}
}
}int best;
void dfs(vector<int>& cookies, vector<int>& bags, int i) {
if (i == (int)cookies.size()) {
int m = 0;
for (int b : bags) m = max(m, b);
best = min(best, m);
return;
}
for (int j = 0; j < (int)bags.size(); j++) {
if (bags[j] + cookies[i] >= best) continue;
bags[j] += cookies[i];
dfs(cookies, bags, i + 1);
bags[j] -= cookies[i];
if (bags[j] == 0) break;
}
}
int distributeCookies(vector<int>& cookies, int k) {
vector<int> bags(k, 0);
best = INT_MAX;
dfs(cookies, bags, 0);
return best;
}Explanation
We hand out bags of cookies to k children and want the child who ends up with the most cookies to have as few as possible. Since each bag can go to any child, we try the assignments with backtracking and keep the best result.
The DFS dfs(i) places bag i into some child's pile bags[j], then moves on to bag i + 1. When all bags are placed, the most-loaded child is max(bags), and we update best if this distribution is fairer.
Two prunes keep it fast. The check if bags[j] + cookies[i] >= best: continue skips any placement that already matches or beats the best answer found so far — it can't improve things. And if bags[j] == 0: break stops trying further empty children, because putting bag i into any one empty pile is the same as any other and would just duplicate work.
We add the bag, recurse, then subtract it back out (the backtracking undo) before trying the next child.
Example: cookies = [8,15,10,20,8], k = 2. One assignment gives one child {8,15,8}=31 and the other {10,20}=30, so the max is 31. No split does better, so the answer is 31.