f*********i
发帖数: 197 | 1 一个int数组A中有2n个数，如何把它分为两个小数组A1 and A2，A1 and A2分别包含n
个数并且数组和最接近。
请问有没有好的解法，多谢 |
d**u
发帖数: 1065 | |
d**u
发帖数: 1065 | |
C***U
发帖数: 2406 | |
w****x
发帖数: 233 | 5 dynamic programming, pseudo-polynomial complexity. |
p*****2
发帖数: 21240 | 6 这题好像以前有人提过。没怎么注意讨论。这次搬个板凳过来学习。 |
t*********7
发帖数: 255 | 7 背包问题...先算SUM/2,然后将数组分两组,DP计算两组书交换之后对两个字数组和的影
响,找出最接近SUM/2的解 |
w****x
发帖数: 2483 | 8
这题解法太难想了, 要是直接给出这个解法别人肯定知道你背过, 而且考这个题就不太
正常
【在 t*********7 的大作中提到】
: 背包问题...先算SUM/2,然后将数组分两组,DP计算两组书交换之后对两个字数组和的影
: 响,找出最接近SUM/2的解
|
p*****2
发帖数: 21240 | 9
我说这题怎么那么熟呢。我用DFS解过
【在 w****x 的大作中提到】
:
: 这题解法太难想了, 要是直接给出这个解法别人肯定知道你背过, 而且考这个题就不太
: 正常
|
g***s
发帖数: 3811 | 10 你要是回答这就是双机调度的简化版本，估计面试官会觉得你问题转换能力不错。
【在 w****x 的大作中提到】
:
: 这题解法太难想了, 要是直接给出这个解法别人肯定知道你背过, 而且考这个题就不太
: 正常
|
p*****2
发帖数: 21240 | 11
大神说说这是啥概念呀。
【在 g***s 的大作中提到】
: 你要是回答这就是双机调度的简化版本，估计面试官会觉得你问题转换能力不错。
|
j********e
发帖数: 1192 | 12 不完全相同，因为限定了每组n个数字。Partition problem没这要求
【在 d**u 的大作中提到】
: NPC问题: http://en.wikipedia.org/wiki/Partition_problem
|
g***s
发帖数: 3811 | 13 我看题没看清，没看到个数一样（每组都要n个）。//shy
这题简单的DP可解。没细想，不知道是否有更优解
b[i] = a[i] - min(a)
bool f(sum,n,k): 前n个元素中，取k个，和是否可能sum
f(sum,n,k) = f(sum-b[n],n-1,k-1) | f(sum,n-1,k)
时间复杂读是
sum(b)/2 * n * n
空间复杂度
sum(b)/2 * 2 * n (第二个参数n只依赖n-1)
不需要个数一样的话,就是双机调度问题的简化，任何一个任务在两台机器上需要的时
间一样。让总时间最小化。
【在 p*****2 的大作中提到】
:
: 大神说说这是啥概念呀。
|
d******3
发帖数: 232 | 14 How about Simulated Annealing?
n
【在 f*********i 的大作中提到】
: 一个int数组A中有2n个数，如何把它分为两个小数组A1 and A2，A1 and A2分别包含n
: 个数并且数组和最接近。
: 请问有没有好的解法，多谢
|
