碰到了一道optimal partition的题想请教大家

题目如下
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 numberof 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;
代码如下:

1. import java.util.*;
   
2. 
   
3. /* http://www.1point3acres.com/bbs/thread-144544-1-1.html
   
4. */
   
5. 
   
6. class OptimalPartition {
   
7. 
   
8.     public List<List<Integer>> partitions(int[] nums, int k) {
   
9.         List<List<Integer>> result = new ArrayList<>();
   
10.         if (nums == null || nums.length == 0) return result;
    
11.         int n = nums.length;
    
12. 
    
13.         // Sort array, then collapse it.
    
14.         Arrays.sort(nums);
    
15.         List<Integer> collapsed = new ArrayList<>();
    
16.         int[] info = collapse(nums, collapsed);
    
17.         int max = info[0], sum = info[1];
    
18. 
    
19.         // Use binary search to find appropriate value;
    
20.         int rangeMin = max; // The minimum value of number of elements in a given bin
    
21.         int rangeMax = sum; // The maximum value of number of elements in a given bin
    
22.         int num = binarySearch(collapsed, rangeMin, rangeMax, k);
    
23. 
    
24.         // Finish the partition using 'num';
    
25.         int i = 0;
    
26.         while (i < n) {
    
27.             List<Integer> item = new ArrayList<>();
    
28.             int counter = 0;
    
29.             while (counter++ < num && i<n) {
    
30.                 item.add(nums[i++]);
    
31.             }
    
32.             result.add(item);
    
33.         }
    
34.         return result;
    
35.     }
    
36. 
    
37.     /* After sorting the original array, convert it into another array, element of which
    
38.      * is the number of consecutive equal number.
    
39.      */
    
40.     private int[] collapse(int[] nums, List<Integer> collapsed) {
    
41.         int prev = nums[0];
    
42.         int counter = 1;
    
43.         int sum = 0, max = 0;
    
44.         for (int i=1; i<nums.length; ++i) {
    
45.             if (nums[i] == prev) counter++;
    
46.             else {
    
47.                 collapsed.add(counter);
    
48.                 max = Math.max(max, counter);
    
49.                 sum+=counter;
    
50.                 counter = 1;
    
51.                 prev = nums[i];
    
52.             }
    
53.         }
    
54.         collapsed.add(counter);
    
55.         max = Math.max(max, counter);
    
56.         sum+=counter;
    
57.         return new int[] {max, sum};
    
58.    }
    
59. 
    
60.     private int binarySearch(List<Integer> collapsed, int start, int end, int k) {
    
61.         if (start > end) return -1;
    
62.         int mid = start + (end - start)/2;
    
63.         if (partition(collapsed, mid, k)) {
    
64.             int left = binarySearch(collapsed, start, mid-1, k);
    
65.             if (left != -1) return left;
    
66.             return mid;
    
67.         }
    
68.         return binarySearch(collapsed, mid+1, end, k);
    
69.     }
    
70. 
    
71.     // Greedily allocate element from left to right using given 'maximum number of elements in a bin'
    
72.     private boolean partition(List<Integer> collapsed, int max, int k) {
    
73.         int n = collapsed.size();
    
74.         int counter = 0;
    
75.         int partitionNum = 0;
    
76.         for (int i=0; i<n; ++i) {
    
77.             if (counter+collapsed.get(i)<=max) {
    
78.                 counter += collapsed.get(i);
    
79.             } else {
    
80.                 counter = 0;
    
81.                 i--;
    
82.                 partitionNum++;
    
83.             }
    
84.         }
    
85.         partitionNum++;
    
86.         return partitionNum<=k;
    
87.     }
    
88. 
    
89.     public static void main(String[] args) {
    
90.         OptimalPartition o = new OptimalPartition();
    
91.         for (List<Integer> part: o.partitions(new int[] {5, 2, 3, 6, 1, 6}, 3)) {
    
92.             System.out.println(part);
    
93.         }
    
94.         for (List<Integer> part: o.partitions(new int[] {1, 1, 1, 1, 1, 1}, 3)) {
    
95.             System.out.println(part);
    
96.         }
    
97.         for (List<Integer> part: o.partitions(new int[] {1, 1, 1, 1, 2, 2, 3}, 2)) {
    
98.             System.out.println(part);
    
99.         }
    
100.     }
     
101. }

复制代码

如果感觉我解释的不够清楚，可以参考这里:最大值最小值问题http://blog.csdn.net/nanjunxiao/article/details/8145971

不确定是否正确，求大神拍砖。

gorilazz 发表于 2015-10-18 13:00
DP应该也可以。
先记录每个元素的出现次数(key, count)， 然后按照key排序存一个数组A
用L记录用最优解将 ...

附上code:

class Solution(object):
    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[i][0] = L[i-1][0] + A[i]
            G[i][0] = L[i][0]

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

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

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

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

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

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的个数

自己顶一下

sorting?

hwberg 发表于 2015-10-17 02:45
sorting?

嗯，我也想是先要sort。。然后呢？？

根本看不懂什么意思...

这个题感觉说得不是很清楚。”minimize the maximum number of items in any bin“ 这句话本身有歧义。如果把6个数字平均分配到3个bin中，每个bin中”number of items“是2。那么maximum number of items只能理解为”最长的bin的长度“，此处即M = max(2, 2, 2)。然后我们要minimize这个M。那很简单，只要往N个bin里均匀分配item就好了，分配什么item不重要。

但是看你的例子的结果是排好序的，所以我想应该不是上面的那个意思。但是我又无法从题目中推出其他的理解了， unless some modifications are made to the original description. e.g. change 'maximum NUMBER of items' to 'maximum items' (sorry I suddenly lost my input method).

stellari 发表于 2015-10-17 09:24
这个题感觉说得不是很清楚。”minimize the maximum number of items in any bin“ 这句话本身有歧义。如果 ...

这句话没有任何歧义。

题意是minimize所有bin中元素个数的最大值。因为元素可以重复，所以并不一定能平均分配。你看看我给的测试例子，如果要求三个bin，元素是1，1，1，1，1，1。你可以做到每个bin里放两个么？注意bin是non-overlapping, consecutive。

maplain 发表于 2015-10-17 10:07
这句话没有任何歧义。

题意是minimize所有bin中元素个数的最大值。因为元素可以重复，所以并不一定能 ...

Right, thanks. Looks like I did understand the "minimize the maximum number..." part correctly, but overlooked the "non-overlapping and consecutive" (though I still find "consecutive" slightly ambiguous but your explanation makes sense).

stellari 发表于 2015-10-17 10:25
Right, thanks. Looks like I did understand the "minimize the maximum number..." part correctly, bu ...

My pleasure.