h******2
发帖数: 13 | 1 问一道微软的面试题:
有2*N个文件，文件的大小保存在size[2*N]中。然后想要分成N份（每一份可以有1或者
多个文件),要使这N份中的文件size之和的最大值最小，如何实现? | w****x
发帖数: 2483 | | s****r
发帖数: 5546 | 3 This is similar to Huffman-code. Put the size array into
a min-priority queue. Pick the top2, add them and put the sum
back into the priority queue, until there are N elements left.
【在 h******2 的大作中提到】
: 问一道微软的面试题:
: 有2*N个文件，文件的大小保存在size[2*N]中。然后想要分成N份（每一份可以有1或者
: 多个文件),要使这N份中的文件size之和的最大值最小，如何实现?
| n*******w
发帖数: 687 | 4 lz有没有例子?不太懂题目。但是感觉不是贪心就是DP。 | j********e
发帖数: 1192 | 5 这是greedy的做法，不能保证最优吧.
例如1, 2, 3, 6, 7分两组，这样做的结果会得到(1,2,3,6), (7)吧？
当然，这肯定是个NP问题，这个greedy解法也不错了，应该能保证
是2/1-aprroximation了。
【在 s****r 的大作中提到】
: This is similar to Huffman-code. Put the size array into
: a min-priority queue. Pick the top2, add them and put the sum
: back into the priority queue, until there are N elements left.
| w****x
发帖数: 2483 | | b***e
发帖数: 1419 | 7 This is equivalent to partition or knapsack.
【在 h******2 的大作中提到】
: 问一道微软的面试题:
: 有2*N个文件，文件的大小保存在size[2*N]中。然后想要分成N份（每一份可以有1或者
: 多个文件),要使这N份中的文件size之和的最大值最小，如何实现?
| l****i
发帖数: 396 | | d********f
发帖数: 43471 | 9 N份中的文件size之和的最大值最小
【在 l****i 的大作中提到】
: 没看明白 怎么分size不是都不变么？
| m******d
发帖数: 25 | 10 size从大到小排列，每次把文件放到当前文件和最小的组里。1, 2, 3, 6, 7分两组的
情况：
1）7
2）7，6
3）7，6 3
4）7 2，6 3
5）7 2 1， 6 3
用heap找文件和最小值。 | | | r********g
发帖数: 1351 | 11 没明白lz的意思是把2N份文件文成N份，还是分成2份。。
【在 m******d 的大作中提到】
: size从大到小排列，每次把文件放到当前文件和最小的组里。1, 2, 3, 6, 7分两组的
: 情况：
: 1）7
: 2）7，6
: 3）7，6 3
: 4）7 2，6 3
: 5）7 2 1， 6 3
: 用heap找文件和最小值。
| E*******0
发帖数: 465 | 12 我觉得是正解。
【在 s****r 的大作中提到】
: This is similar to Huffman-code. Put the size array into
: a min-priority queue. Pick the top2, add them and put the sum
: back into the priority queue, until there are N elements left.
| w****x
发帖数: 2483 | 13
So do 偶
【在 E*******0 的大作中提到】
: 我觉得是正解。
| E*******0
发帖数: 465 | 14 Sorry, I found it is not correct.
Counter example:
2,4,4,5
1st step: 4, 5, 6
2st step: 6, 9
which maximum file size is 9.
but we can found (2,5) and (4,4) with smaller maximum file size of 8.
【在 w****x 的大作中提到】
:
: So do 偶
| E*******0
发帖数: 465 | 15 result should be bigger than or equal to 2*average of (2*N array). | l****3
发帖数: 150 | 16 the first step result should be 2, 8, 5
【在 E*******0 的大作中提到】
: Sorry, I found it is not correct.
: Counter example:
: 2,4,4,5
: 1st step: 4, 5, 6
: 2st step: 6, 9
: which maximum file size is 9.
: but we can found (2,5) and (4,4) with smaller maximum file size of 8.
| h******2
发帖数: 13 | 17 能具体解释一下吗？
【在 b***e 的大作中提到】
: This is equivalent to partition or knapsack.
| E*******0
发帖数: 465 | 18 why?
【在 l****3 的大作中提到】
: the first step result should be 2, 8, 5
| l****3
发帖数: 150 | 19 from 2 4 4 5
pick 5, now we have 5 0
pick 4, now we have 5 4
pick 4, now we have 5 8
pick 2, now 7 8
....
【在 E*******0 的大作中提到】
: why?
| E*******0
发帖数: 465 | 20 Would you please write your solution for 25, 13,12,7,7,7 and 25,24,23,1,1,1
respectively?
And [slower]'s algorithms is for min-priority queue.
【在 l****3 的大作中提到】
: from 2 4 4 5
: pick 5, now we have 5 0
: pick 4, now we have 5 4
: pick 4, now we have 5 8
: pick 2, now 7 8
: ....
| | | b***e
发帖数: 1419 | 21 Assuming you have 2*n items, the sum of which is S. Then you can add
2000000 * n items, each of which is of value S/4. This way you are pretty
much bound to divide the S into two halfs, which is a partition/knapsack
problem.
【在 h******2 的大作中提到】
: 能具体解释一下吗？
| s******t
发帖数: 229 | 22 先sorting一下，首跟尾一组，然后把首跟尾去掉，再把首跟尾一组，递归。。。。 | s******t
发帖数: 229 | 23 32
26
1
【在 E*******0 的大作中提到】
: Would you please write your solution for 25, 13,12,7,7,7 and 25,24,23,1,1,1
: respectively?
: And [slower]'s algorithms is for min-priority queue.
| c*******d
发帖数: 131 | 24 1 2 3 7 就不对
好像只有megamind的解法靠谱
【在 s******t 的大作中提到】
: 先sorting一下，首跟尾一组，然后把首跟尾去掉，再把首跟尾一组，递归。。。。
| m*****k
发帖数: 731 | 25 25
25, 13
25,13,12
25,13, 12+7
25, 13+7, 12+7
25, 13+7, 12+7+7
我也觉得megamind的解法靠谱，求证明。
1
【在 E*******0 的大作中提到】
: Would you please write your solution for 25, 13,12,7,7,7 and 25,24,23,1,1,1
: respectively?
: And [slower]'s algorithms is for min-priority queue.
| E*******0
发帖数: 465 | 26 举个反例：
25， 25， 19， 15， 14, 13， 12， 11，10， 1
正解： 25， 25， （13，12）， （14，11），(15，10）, (19,1)
按照megamind的算法：
1) 25,25,19,15,14
2) 25, 25, 19, 15, (14,13)
3) (14,13), 25, 25, 19, (15, 12)
4) (14,13), (15,12), 25,25, (19,11)
5) (19,11), (14,13), (15,12), (25,10), 25
6) (19,11), (14,13), (15,12), (25,10), (25,1)
【在 m******d 的大作中提到】
: size从大到小排列，每次把文件放到当前文件和最小的组里。1, 2, 3, 6, 7分两组的
: 情况：
: 1）7
: 2）7，6
: 3）7，6 3
: 4）7 2，6 3
: 5）7 2 1， 6 3
: 用heap找文件和最小值。
| E*******0
发帖数: 465 | 27 我目前还没有找到一个方法解决这个问题。
我有一些基本的clue供大家参考：
1,如果2*N个数都相等的话，Min(Sum)=2*val;
2,如果2*N个数有一个特别大，其大都很小，Min(sum)=max value;
3,如果2*N个数是[1,2,3,...,N,N+1, ..., 2*N], Min(Sum)=2*N+1=2* average. | E*******0
发帖数: 465 | 28 2， 第三种情况分组分别是头尾相连。
3， 但是还有一种情况是，刚好三个三个为一组，组成平均数，还有若干个平均数数值。
4， 刚好四个四个为一组，组成平均数，还有若干个平均数。
5， 刚好五个五个为一组，组成平均数，还有若干个平均数。
依此类推，越来越发现这个问题是NP问题，不知道大家有什么看法。 | E*******0
发帖数: 465 | 29 我有一个假设：
Min(sum)>=Max[2*average, MaxValu];
int goal=Max[2*average, MaxValu];
同样排序，用greedy algorithm找到尽可能多的组合which sum equals goal. | E*******0
发帖数: 465 | 30 大家再看看这个人说的，貌似有点道理，我再想想啊。
【在 b***e 的大作中提到】
: Assuming you have 2*n items, the sum of which is S. Then you can add
: 2000000 * n items, each of which is of value S/4. This way you are pretty
: much bound to divide the S into two halfs, which is a partition/knapsack
: problem.
| | | t******e
发帖数: 98 | 31 这个反例不对吧，没有把文件分为5组。是不是应该下面这样？
(25) (25,1) (15, 14) (12, 11, 10) (13, 19)
这题只能想到状态压缩DP解法。
【在 E*******0 的大作中提到】
: 举个反例：
: 25， 25， 19， 15， 14, 13， 12， 11，10， 1
: 正解： 25， 25， （13，12）， （14，11），(15，10）, (19,1)
: 按照megamind的算法：
: 1) 25,25,19,15,14
: 2) 25, 25, 19, 15, (14,13)
: 3) (14,13), 25, 25, 19, (15, 12)
: 4) (14,13), (15,12), 25,25, (19,11)
: 5) (19,11), (14,13), (15,12), (25,10), 25
: 6) (19,11), (14,13), (15,12), (25,10), (25,1)
| t******e
发帖数: 98 | 32 写个思路抛砖引玉了。
a[2*N]表示文件大小数组，设f(int[] a, int set, int k)表示状态，set是一个
binary integer表示a[]的一个子集，k表示将a[]的这个子集分成k份,状态转移方程是
f(a[], set, k) = min{ max{sum(a[]： for element a[i] in a subset set' of set
), f(a, set - set', k-1)}: for all subset set' of set }. 边界条件是f(a[],
set, 1) = sum(a[]: for elements a[i] in set). 解法的限制是N不能太大(<=10)，
否则内存吃不消。 | E*******0
发帖数: 465 | 33 不好意思，搞错了。
就是说正解和那个算法解不一样。
【在 t******e 的大作中提到】
: 这个反例不对吧，没有把文件分为5组。是不是应该下面这样？
: (25) (25,1) (15, 14) (12, 11, 10) (13, 19)
: 这题只能想到状态压缩DP解法。
| E*******0
发帖数: 465 | 34 能否写的详细点？
set
【在 t******e 的大作中提到】
: 写个思路抛砖引玉了。
: a[2*N]表示文件大小数组，设f(int[] a, int set, int k)表示状态，set是一个
: binary integer表示a[]的一个子集，k表示将a[]的这个子集分成k份,状态转移方程是
: f(a[], set, k) = min{ max{sum(a[]： for element a[i] in a subset set' of set
: ), f(a, set - set', k-1)}: for all subset set' of set }. 边界条件是f(a[],
: set, 1) = sum(a[]: for elements a[i] in set). 解法的限制是N不能太大(<=10)，
: 否则内存吃不消。
| g***s
发帖数: 3811 | 35 这个解法是指数级别的
DP很少会用subset作为状态。
【在 E*******0 的大作中提到】
: 能否写的详细点？
:
: set
| f*********2
发帖数: 25 | 36 This idea works. I illustrate in a slightly different way and hope it can be
easily understood.
Assume that we need to group 1, 2, 3, 6, 7 by two groups.
(1) In the very beginning, separate the biggest two numbers into different
groups.
Group 1: 7
Group 2: 6
(2) Next, we add 3 to one of the above groups. It is clear that 3 should be
added to 6, otherwise, if we had added 3 to 7, the sum would have changed to
10, not as optimal as 6 + 3 = 9.
Group 1: 7
Group 2: 6 + 3 = 9
(3) Add 2 to one of the above groups.Now Group 1 has smaller sum, so add 2
to the smallest group.
Group 1: 7 + 2 = 9
Group 2: 6 + 3 = 9.
(4) Add 1 to one of the above groups. Since both group has value 9, number 1
can be added to either one of them. So the result turns to be
Group 1: 7 + 2 + 1 = 10
Group 1: 6 + 3 = 9.
Answer: 10
Example 2: Divide 25,13,12,7,7,7 into three groups (from Erica3740 (秋泥针))
(Step 1) Initialize the three groups with the biggest three numbers.
Group 1: 25
Group 2: 13
Group 3: 12
(Step 2) Add 7 to one of the above groups. Group 3 has the smallest element
and so is the best choice.After addition, we have
Group 1: 25
Group 3: 12 + 7 = 19
Group 2: 13
(Step 3) Add 7 to one group. Group 2 has the smallest element and so is the
best choice.
Group 1: 25
Group 3: 12 + 7 = 19
Group 2: 13 + 7 = 20
(Step 4) Add 7 to one group. Group 3 has the smallest element and so is the
best choice.
Group 1: 25
Group 3: 12 + 7 + 7 = 19 + 7 = 26
Group 2: 13 + 7 = 20
Answer: 26
Example 3: Divide 25,24,23,1,1,1 into 3 groups
25
24 + 1 = 25
23 + 1 + 1 = 25
Answer: 25
【在 m******d 的大作中提到】
: size从大到小排列，每次把文件放到当前文件和最小的组里。1, 2, 3, 6, 7分两组的
: 情况：
: 1）7
: 2）7，6
: 3）7，6 3
: 4）7 2，6 3
: 5）7 2 1， 6 3
: 用heap找文件和最小值。
| b*****e
发帖数: 131 | 37 用这个原理：假设数组a[n] is sorted. 则最优解发生于下列两情况之一：1. a[n-1]
单独组成一份 2. a[n-1] 与 a[0] 组成一份。
由上可得递归算法如下：
int minUnit(int a[], int n, int nUnit)
{
if(n == 1)
return a[0];
if(nUnit == 1)
return SUM(a, n);
int min1 = MAX(a[n-1], minUnit(a, n-1, nUnit-1)); // a[n-1]单独一份
int min2 = MAX(a[n-1]+a[0], minUnit(a+1, n-2, nUnit-1)); // a[n-1] 与 a[
0] 组成一份
return MIN(min1, min2);
} | l**********o
发帖数: 260 | 38 25 13 12 7 7 7结果应该是
25 （13 12）（7 7 7）
这个解法是错的
be
be
to
★ 发自iPhone App: ChineseWeb 7.3
【在 f*********2 的大作中提到】
: This idea works. I illustrate in a slightly different way and hope it can be
: easily understood.
: Assume that we need to group 1, 2, 3, 6, 7 by two groups.
: (1) In the very beginning, separate the biggest two numbers into different
: groups.
: Group 1: 7
: Group 2: 6
: (2) Next, we add 3 to one of the above groups. It is clear that 3 should be
: added to 6, otherwise, if we had added 3 to 7, the sum would have changed to
: 10, not as optimal as 6 + 3 = 9.
| c*******d
发帖数: 131 | 39 提供一个想法，我暂时还没想到反例：
假设我们有N个bag来装这2N个数，首先将N个bag全部初始化为0， 用一个max变量实时
记录这N个bag的最大的那个, 将2N个数字从大到小排列，然后按照如下规则将这个2N个
数一个一个装袋：
case 1: 从最大的bag开始search，找到第一个这样的bag：满足这个bag的和加上这个
数不大于现在的max，如果能找到这个bag，就把这个数装到这个bag里面。
case 2： 找不到这样的bag，这说明已经search到最后那个最小的bag了(并且这个也不
满足case1的条件)，如果这样的话，就将现在这个数加入这个bag，并且更新max为这个
bag的值。
example： 25 13 12 7 7 7
bags： 0 0 0， max = 0.
25： 25 0 0, max = 25. (case 2)
13: 25 13 0, max = 25. (case 1)
12: 25 (13,12) 0, max = 25. (case 1)
7: 25 (13,12) 7, max = 25. (case 1)
7: 25 (13,12) (7,7), max = 25 (case 1)
7: 25 (13,12) （7，7，7）max = 25 (case 1) | o********d
发帖数: 13 | 40 感觉是DP啊，考虑最大的一个文件，假设这个大小是a,那么可以知道只有两种情况：a
可能是单独的一个文件为一组，也可能是两个文件为一组。
如果包含a的那一组有3个文件（a,b,c）,那么必然有一个文件d(d
显然a+b+c>a+b, a+b+c>d+c
如果a的那一组有两个文件（a,b）,并且b不是最小的，那么假设c为最小，如果包含c的
一组文件数大于2，那么一定有一个文件d单独为一组，那么如果交换a和d,可以知道a+b
>a,a+b>b+d.所以这种情况可以转化为a单独一组，
如果包含c的一组文件有两个（c,d）那么我们可以知道b>c,a>d，显然这样不是最优的，
如果c单独为一组，那么显然也有a+b>a+c,a+b>b
假设为排序序列的话，那么是不是就有opt(i,j)=min（max(size(i),opt(i,j-1)),max(
size(i)+size(j),opt(i+1,j-1))）?
【在 h******2 的大作中提到】
: 问一道微软的面试题:
: 有2*N个文件，文件的大小保存在size[2*N]中。然后想要分成N份（每一份可以有1或者
: 多个文件),要使这N份中的文件size之和的最大值最小，如何实现?
| | | l**********o
发帖数: 260 | 41 参考31楼给的例子，是不是有点问题。
★ 发自iPhone App: ChineseWeb 7.3
【在 c*******d 的大作中提到】
: 提供一个想法，我暂时还没想到反例：
: 假设我们有N个bag来装这2N个数，首先将N个bag全部初始化为0， 用一个max变量实时
: 记录这N个bag的最大的那个, 将2N个数字从大到小排列，然后按照如下规则将这个2N个
: 数一个一个装袋：
: case 1: 从最大的bag开始search，找到第一个这样的bag：满足这个bag的和加上这个
: 数不大于现在的max，如果能找到这个bag，就把这个数装到这个bag里面。
: case 2： 找不到这样的bag，这说明已经search到最后那个最小的bag了(并且这个也不
: 满足case1的条件)，如果这样的话，就将现在这个数加入这个bag，并且更新max为这个
: bag的值。
: example： 25 13 12 7 7 7
|
|
