i******w
发帖数: 407 | 1 长度为2n的无序数组， 怎么分成2个长度为n的子数组，使得2个子数组的和之差最小？
被要求用polynomial的time complexity。死活没想出来。
请大牛们帮忙看看，谢谢 |
r**a
发帖数: 31 | 2 不可能，这是个NPHard问题 http://en.wikipedia.org/wiki/Partition_problem
有伪多项式的算法（复杂度和值的范围有关），如果面试官要纯多项式的算法，就喷他
一脸
【在 i******w 的大作中提到】
: 长度为2n的无序数组， 怎么分成2个长度为n的子数组，使得2个子数组的和之差最小？
: 被要求用polynomial的time complexity。死活没想出来。
: 请大牛们帮忙看看，谢谢
|
f*****e
发帖数: 2992 | 3 什么公司？太牛了！
【在 i******w 的大作中提到】
: 长度为2n的无序数组， 怎么分成2个长度为n的子数组，使得2个子数组的和之差最小？
: 被要求用polynomial的time complexity。死活没想出来。
: 请大牛们帮忙看看，谢谢
|
w****a
发帖数: 710 | |
m****1
发帖数: 41 | 5 比wiki上的还要难一点。因为需要分成等长的两个set。 所以还需要一个变量表示set
的长度。P[N/2][n][n/2] 三维dp? |
w****a
发帖数: 710 | 6 好吧 他可能就是子集的意思，不然就只有一种情况了 |
m*****k
发帖数: 731 | 7 猜想：
sort first,
then s[0],s[n-1] go to S1,
s[1],s[n-2] go to S2,
s[2],s[n-3] go to S1,
...
when n is odd,
s[n-1] go to S1, s[n] go to S2 |
a********m
发帖数: 15480 | 8 赞！
【在 r**a 的大作中提到】
: 不可能，这是个NPHard问题 http://en.wikipedia.org/wiki/Partition_problem
: 有伪多项式的算法（复杂度和值的范围有关），如果面试官要纯多项式的算法，就喷他
: 一脸
|
a********m
发帖数: 15480 | 9 1，1，2，2，2，100。
【在 m*****k 的大作中提到】
: 猜想：
: sort first,
: then s[0],s[n-1] go to S1,
: s[1],s[n-2] go to S2,
: s[2],s[n-3] go to S1,
: ...
: when n is odd,
: s[n-1] go to S1, s[n] go to S2
|
h**********c
发帖数: 4120 | 10 假设平衡没有打破
再进来两个数，调整
可能近似
能不能用数学归纳法证明
或者反例 |
|
|
h**********c
发帖数: 4120 | 11 如果每次调整都是 log n，那在数学上就是一件很美的事情 |
h**********c
发帖数: 4120 | |
i*******e
发帖数: 114 | 13 赞喷他一脸。
【在 r**a 的大作中提到】
: 不可能，这是个NPHard问题 http://en.wikipedia.org/wiki/Partition_problem
: 有伪多项式的算法（复杂度和值的范围有关），如果面试官要纯多项式的算法，就喷他
: 一脸
|
h**********c
发帖数: 4120 | 14 没太看懂polynomial 和big O 啥关系 |
x*******9
发帖数: 138 | 15 小数据用背包
大数据上集群吧就。。。（逗
==
顺便围观roba大神 |
B********4
发帖数: 7156 | 16 An algorithm is said to be of polynomial time if its running time is upper
bounded by a polynomial expression in the size of the input for the
algorithm, i.e., T(n) = O(n^k) for some constant k.
我的理解， O(n^2)就算polynomial time complexity.
【在 h**********c 的大作中提到】
: 没太看懂polynomial 和big O 啥关系
|
a*****2
发帖数: 96 | 17 V^k(i,j) = 1 if there exists k elements in {a_1,a_2,...,a_i} summing up to j
v^k(i,j) = 0 otherwise,
i = k,...,2n
j = 1,2,...,sum^k
where sum^k is the maximum sum of k elements in arr
DP:
v^k(i,j) = max(v^k(i-1,j),v^(k-1)(i-1,j-a_i))
Results:
min abs( j - sum(arr)/2), j = 1,...,sum^n and v^n(2n,j) = 1 |
