B*******1
发帖数: 2454 | 1 careercup上面看的
Partition a set of numbers into two such that difference between their sum
is minimum, and both sets have equal number of elements.
For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff = 17
-13=4.
Does greedy work here? First sorting, and then picking smallest and largest
to fall in set 1, and picking 2nd smallest and 2nd largest to fall in set 2.
I was asked to prove which I failed :( |
g*****i
发帖数: 2162 | 2 partition problem变种,应该可以用subset problem的dp solution来做,wiki上说的.
greedy方法的approximation factor是4/3,很接近了.
楼主我觉得你老是钻研这种难题没啥必要,面试这种题目出现的概率极低,出了面试官也
会引导你的. |
B*******1
发帖数: 2454 | 3 没有研究，careercup上的google的怎么都这么难。 |
y*******g
发帖数: 6599 | 4 careercup 估计是假题目吧
我觉得glassdoor好的多，
【在 B*******1 的大作中提到】
: 没有研究，careercup上的google的怎么都这么难。
|
B*******1
发帖数: 2454 | 5 是啊？ 而且看了这几个我贴的这么难的都是google india的。 |
D*******e
发帖数: 151 | 6 有人跟我说，随机置换两边的数（只要让结果变好就换）是最快的 |
c****p
发帖数: 6474 | 7 greedy，容易达到local optimal.
【在 D*******e 的大作中提到】
: 有人跟我说，随机置换两边的数（只要让结果变好就换）是最快的
|
i**d
发帖数: 357 | 8 这应该是一个dp题。
等价于 在数组中找出 len/2个数，使得和在不大于 sum/2时，最大化. |
c****x
发帖数: 61 | 9 必然是假的
子集和(NPC) => 二等分 => 二等分且两边元素个数相等 => minimum difference is 0
in this problem
17
largest
2.
【在 B*******1 的大作中提到】
: careercup上面看的
: Partition a set of numbers into two such that difference between their sum
: is minimum, and both sets have equal number of elements.
: For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff = 17
: -13=4.
: Does greedy work here? First sorting, and then picking smallest and largest
: to fall in set 1, and picking 2nd smallest and 2nd largest to fall in set 2.
: I was asked to prove which I failed :(
|
f****4
发帖数: 1359 | 10 Genetic algorithm 就干这个事情的
【在 D*******e 的大作中提到】
: 有人跟我说，随机置换两边的数（只要让结果变好就换）是最快的
|
