Given cookies where cookies[i] is the number of cookies in the i-th bag and an integer k, distribute the bags among k children so that the unfairness, defined as the maximum cookies any child gets, is minimized. Pattern focus: Bitmask DP. Try all subsets assigned to one child and memoize by the remaining bag mask.
cookies = array of bag sizes, k = number of children
minimum possible unfairness
Example 1:
Input:
cookies = [1,2,3] k = 2
Output:
3
Explanation:
Give [1,2] to one child and [3] to the other; the maximum load is 3.
Example 2:
Input:
cookies = [8,15,10,20,8] k = 2
Output:
31
Explanation:
This is a standard benchmark case for this problem.
Example 3:
Input:
cookies = [6,1,3,2,2,4,1,2] k = 3
Output:
7
Explanation:
A balanced distribution can keep the maximum load at 7.