Massive Algorithms: Optimal Partition Array

http://www.1point3acres.com/bbs/thread-144544-1-1.html
Given a list of integer items, we want to partition the items into at most N non-overlapping, consecutive bins, in a way that minimizes the maximum number of items in any bin.
For example, suppose we are given the items (5, 2, 3, 6, 1, 6), and we want 3bins. We can optimally partition these as follows:
n < 3: 1, 2 (2 items)
3 <= n < 6: 3, 5 (2 items)
6 <= n: 6, 6 (2 items)
Every bin has 2 items, so we can’t do any better than that.
Your task: write a program to partition a set of input items.
Example input:
N ＝ 3
5
2
3
6
1
6
Example output:
12
35
66

1. sort;
2. 输出相同元素的个数，组成一个新的array；
3. 针对新的array做minmax partition;
minmax partition核心思想是二分法+贪心:
      1. 找到每个bin中元素和(新的这个array里一个bin中的所有“元素和”表明原始array中对应bin中元素的个数)的可能区间范围；
         1. min是新的array中最大值；
         2. max是新的array中所有元素的和；
      2. 二分搜索这个区间中的值v是否能够得到满足题意的划分，判断时只需要贪心地从左向右添加元素直至达到v;

class OptimalPartition {
public List<List<Integer>> partitions(int[] nums, int k) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) return result;
int n = nums.length;
// Sort array, then collapse it.
Arrays.sort(nums);
List<Integer> collapsed = new ArrayList<>();
int[] info = collapse(nums, collapsed);
int max = info[0], sum = info[1];
// Use binary search to find appropriate value;
int rangeMin = max; // The minimum value of number of elements in a given bin
int rangeMax = sum; // The maximum value of number of elements in a given bin
int num = binarySearch(collapsed, rangeMin, rangeMax, k);
// Finish the partition using 'num';
int i = 0;
while (i < n) {
List<Integer> item = new ArrayList<>();
int counter = 0;
while (counter++ < num && i<n) {
item.add(nums[i++]);
}
result.add(item);
}
return result;
}
/* After sorting the original array, convert it into another array, element of which
* is the number of consecutive equal number.
*/
private int[] collapse(int[] nums, List<Integer> collapsed) {
int prev = nums[0];
int counter = 1;
int sum = 0, max = 0;
for (int i=1; i<nums.length; ++i) {
if (nums[i] == prev) counter++;
else {
collapsed.add(counter);
max = Math.max(max, counter);
sum+=counter;
counter = 1;
prev = nums[i];
}
}
collapsed.add(counter);
max = Math.max(max, counter);
sum+=counter;
return new int[] {max, sum};
}
private int binarySearch(List<Integer> collapsed, int start, int end, int k) {
if (start > end) return -1;
int mid = start + (end - start)/2;
if (partition(collapsed, mid, k)) {
int left = binarySearch(collapsed, start, mid-1, k);
if (left != -1) return left;
return mid;
}
return binarySearch(collapsed, mid+1, end, k);
}
// Greedily allocate element from left to right using given 'maximum number of elements in a bin'
private boolean partition(List<Integer> collapsed, int max, int k) {
int n = collapsed.size();
int counter = 0;
int partitionNum = 0;
for (int i=0; i<n; ++i) {
if (counter+collapsed.get(i)<=max) {
counter += collapsed.get(i);
} else {
counter = 0;
i--;
partitionNum++;
}
}
partitionNum++;
return partitionNum<=k;
}
public static void main(String[] args) {
OptimalPartition o = new OptimalPartition();
for (List<Integer> part: o.partitions(new int[] {5, 2, 3, 6, 1, 6}, 3)) {
System.out.println(part);
}
for (List<Integer> part: o.partitions(new int[] {1, 1, 1, 1, 1, 1}, 3)) {
System.out.println(part);
}
for (List<Integer> part: o.partitions(new int[] {1, 1, 1, 1, 2, 2, 3}, 2)) {
System.out.println(part);
}
}
}

DP应该也可以。
先记录每个元素的出现次数(key, count)，然后按照key排序存一个数组A
用L[i,k]记录用最优解将第0-i个元素放到k个bin里时的最后一个bin包含的元素个数，G[i,k]记录最大bin里的元素个数
更新L[i,k]和G[i,k]要做以下判断
如果L[i-1, k]+A[i]<=G[i-1,k]，那么最优放法就是L[i,k]=L[i-1,k]+A[i], G[i,k]=G[i-1,k]
如果L[i-1,k]+A[i]>G[i-1,k]，那么就可能有两种放法，最优放法要取其中之一：
方法1: 前面i-1个元素放到k个bin里，然后元素i也放到bin k里，bin k的元素总数是 s1 = L[i-1,k]+A[k]
方法2: 前面i-1个元素放到k-1个bin里，然后元素i单独放到bin k里， bin k的元素总数是 s2 = A[k]
如果s1<max(s2,G[i-1,k-1])，那就选方法1，L[i,k] = L[i-1,k]+A[k], G[i,k] = L[i,k]
如果s1>max(s2, G[i-1, k-1])，那就选方法2, L[i,k] = A[k], G[i,k] = max(L[i,k], G[i-1, k-1])
如果s1==max(s2, G[i-1, k-1])，那就随便选1或者2

最后要求的就是G[m-1, n-1], m是distinct元素的个数，n是bin的个数

def placement(self, nums, n):

      numbers = {key:nums.count(key) for key in nums}
      numbers = [(key, numbers[key]) for key in numbers]
      numbers.sort()

      A = [item[1] for item in numbers]

      if len(numbers)<=n:
         return max(A)

      L = [[0]*n for _ in range(len(A))]
      G = [[0]*n for _ in range(len(A))]

      L[0][0] = A[0]
      G[0][0] = A[0]
      for i in range(1, len(A)):
         L[0] = L[i-1][0] + A
         G[0] = L[0]

      for i in range(len(A)):
         if i>=n:
            break
         L = A
         G = max(A[:i+1])

      for i in range(len(A)):
         for j in range(i+1, n):
            L[j] = 0
            G[j] = G

      for i in range(1,len(A)):
         for j in range(1,i):
            if j>=n:
                  break
            tmp = L[i-1][j] + A
            if tmp<=G[i-1][j]:
                  L[j] = tmp
                  G[j] = G[i-1][j]
            elif tmp<=max(G[i-1][j-1], A):
                  L[j] = tmp
                  G[j] = G[i-1][j]
            else:
                  L[j] = A
                  G[j] = max(G[i-1][j-1], A)

      return G[len(A)-1][n-1]

sol = Solution()
nums = [1,1,1,1,1,1]
result = sol.placement(nums, 3)
print(result)

Optimal Partition Array

Labels

Popular Posts