一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 435|回复: 13
收起左侧

[算法题] 碰到了一道optimal partition的题想请教大家

[复制链接] |试试Instant~ |关注本帖
swx1031 发表于 2015-10-17 02:04:55 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 swx1031 于 2015-10-17 02:08 编辑

题目如下
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
**求思路求指导
                                       
                                
                        
               
                                       
                                
                        
               



 楼主| swx1031 发表于 2015-10-17 02:32:31 | 显示全部楼层
自己顶一下
回复 支持 反对

使用道具 举报

 楼主| swx1031 发表于 2015-10-17 03:09:40 | 显示全部楼层

嗯,我也想是先要sort。。然后呢??
回复 支持 反对

使用道具 举报

tailofjune 发表于 2015-10-17 03:58:17 | 显示全部楼层
根本看不懂什么意思...
回复 支持 反对

使用道具 举报

maplain 发表于 2015-10-17 07:53:51 | 显示全部楼层
本帖最后由 maplain 于 2015-10-17 08:02 编辑

我的想法是:
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. /* http://www.1point3acres.com/bbs/thread-144544-1-1.html
  3. */

  4. class OptimalPartition {

  5.     public List<List<Integer>> partitions(int[] nums, int k) {
  6.         List<List<Integer>> result = new ArrayList<>();
  7.         if (nums == null || nums.length == 0) return result;
  8.         int n = nums.length;

  9.         // Sort array, then collapse it.
  10.         Arrays.sort(nums);
  11.         List<Integer> collapsed = new ArrayList<>();
  12.         int[] info = collapse(nums, collapsed);
  13.         int max = info[0], sum = info[1];

  14.         // Use binary search to find appropriate value;
  15.         int rangeMin = max; // The minimum value of number of elements in a given bin
  16.         int rangeMax = sum; // The maximum value of number of elements in a given bin
  17.         int num = binarySearch(collapsed, rangeMin, rangeMax, k);

  18.         // Finish the partition using 'num';
  19.         int i = 0;
  20.         while (i < n) {
  21.             List<Integer> item = new ArrayList<>();
  22.             int counter = 0;
  23.             while (counter++ < num && i<n) {
  24.                 item.add(nums[i++]);
  25.             }
  26.             result.add(item);
  27.         }
  28.         return result;
  29.     }

  30.     /* After sorting the original array, convert it into another array, element of which
  31.      * is the number of consecutive equal number.
  32.      */
  33.     private int[] collapse(int[] nums, List<Integer> collapsed) {
  34.         int prev = nums[0];
  35.         int counter = 1;
  36.         int sum = 0, max = 0;
  37.         for (int i=1; i<nums.length; ++i) {
  38.             if (nums[i] == prev) counter++;
  39.             else {
  40.                 collapsed.add(counter);
  41.                 max = Math.max(max, counter);
  42.                 sum+=counter;
  43.                 counter = 1;
  44.                 prev = nums[i];
  45.             }
  46.         }
  47.         collapsed.add(counter);
  48.         max = Math.max(max, counter);
  49.         sum+=counter;
  50.         return new int[] {max, sum};
  51.    }

  52.     private int binarySearch(List<Integer> collapsed, int start, int end, int k) {
  53.         if (start > end) return -1;
  54.         int mid = start + (end - start)/2;
  55.         if (partition(collapsed, mid, k)) {
  56.             int left = binarySearch(collapsed, start, mid-1, k);
  57.             if (left != -1) return left;
  58.             return mid;
  59.         }
  60.         return binarySearch(collapsed, mid+1, end, k);
  61.     }

  62.     // Greedily allocate element from left to right using given 'maximum number of elements in a bin'
  63.     private boolean partition(List<Integer> collapsed, int max, int k) {
  64.         int n = collapsed.size();
  65.         int counter = 0;
  66.         int partitionNum = 0;
  67.         for (int i=0; i<n; ++i) {
  68.             if (counter+collapsed.get(i)<=max) {
  69.                 counter += collapsed.get(i);
  70.             } else {
  71.                 counter = 0;
  72.                 i--;
  73.                 partitionNum++;
  74.             }
  75.         }
  76.         partitionNum++;
  77.         return partitionNum<=k;
  78.     }

  79.     public static void main(String[] args) {
  80.         OptimalPartition o = new OptimalPartition();
  81.         for (List<Integer> part: o.partitions(new int[] {5, 2, 3, 6, 1, 6}, 3)) {
  82.             System.out.println(part);
  83.         }
  84.         for (List<Integer> part: o.partitions(new int[] {1, 1, 1, 1, 1, 1}, 3)) {
  85.             System.out.println(part);
  86.         }
  87.         for (List<Integer> part: o.partitions(new int[] {1, 1, 1, 1, 2, 2, 3}, 2)) {
  88.             System.out.println(part);
  89.         }
  90.     }
  91. }
复制代码
如果感觉我解释的不够清楚,可以参考这里:最大值最小值问题http://blog.csdn.net/nanjunxiao/article/details/8145971

不确定是否正确,求大神拍砖。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-10-17 09:24:45 | 显示全部楼层
这个题感觉说得不是很清楚。”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).
回复 支持 反对

使用道具 举报

maplain 发表于 2015-10-17 10:07:17 | 显示全部楼层
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。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-10-17 10:25:13 | 显示全部楼层
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).
回复 支持 反对

使用道具 举报

maplain 发表于 2015-10-17 11:09:41 | 显示全部楼层
stellari 发表于 2015-10-17 10:25
Right, thanks. Looks like I did understand the "minimize the maximum number..." part correctly, bu ...

My pleasure.
回复 支持 反对

使用道具 举报

 楼主| swx1031 发表于 2015-10-17 11:10:01 | 显示全部楼层
maplain 发表于 2015-10-17 07:53
我的想法是:
1. sort;
2. 输出相同元素的个数,组成一个新的array;

喔喔,非常感谢地理大神!!受教了。。自己还是太嫩啊。
回复 支持 反对

使用道具 举报

gorilazz 发表于 2015-10-18 13:00:49 | 显示全部楼层
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的个数
回复 支持 反对

使用道具 举报

gorilazz 发表于 2015-10-18 13:26:03 | 显示全部楼层
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[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)
回复 支持 反对

使用道具 举报

 楼主| swx1031 发表于 2015-10-19 05:50:22 | 显示全部楼层
gorilazz 发表于 2015-10-18 13:26
附上code:

class Solution(object):

感谢大神耐心解答!!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 10:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表