i*w
2 楼
长度为2n的无序数组， 怎么分成2个长度为n的子数组，使得2个子数组的和之差最小？
被要求用polynomial的time complexity。死活没想出来。
请大牛们帮忙看看，谢谢
被要求用polynomial的time complexity。死活没想出来。
请大牛们帮忙看看，谢谢
m*i
3 楼
@Chicago
b*g
4 楼
应该算卖家的吧
r*a
5 楼
不可能，这是个NPHard问题 http://en.wikipedia.org/wiki/Partition_problem
有伪多项式的算法（复杂度和值的范围有关），如果面试官要纯多项式的算法，就喷他
一脸
【在 i******w 的大作中提到】
: 长度为2n的无序数组， 怎么分成2个长度为n的子数组，使得2个子数组的和之差最小？
: 被要求用polynomial的time complexity。死活没想出来。
: 请大牛们帮忙看看，谢谢
有伪多项式的算法（复杂度和值的范围有关），如果面试官要纯多项式的算法，就喷他
一脸
【在 i******w 的大作中提到】
: 长度为2n的无序数组， 怎么分成2个长度为n的子数组，使得2个子数组的和之差最小？
: 被要求用polynomial的time complexity。死活没想出来。
: 请大牛们帮忙看看，谢谢
s*7
6 楼
wow, gorgeous !
h*t
7 楼
嗯，卖家送错了算卖家的吧
f*e
8 楼
什么公司？太牛了！
【在 i******w 的大作中提到】
: 长度为2n的无序数组， 怎么分成2个长度为n的子数组，使得2个子数组的和之差最小？
: 被要求用polynomial的time complexity。死活没想出来。
: 请大牛们帮忙看看，谢谢
【在 i******w 的大作中提到】
: 长度为2n的无序数组， 怎么分成2个长度为n的子数组，使得2个子数组的和之差最小？
: 被要求用polynomial的time complexity。死活没想出来。
: 请大牛们帮忙看看，谢谢
c*d
9 楼
芝加哥美女好多阿~~~顶不住压力的要撤退了
【在 m****i 的大作中提到】
: @Chicago
【在 m****i 的大作中提到】
: @Chicago
w*a
10 楼
patition问题是子集吧，这里是子数组
C9
11 楼
美眉，让我应征一个吧
【在 m****i 的大作中提到】
: @Chicago
【在 m****i 的大作中提到】
: @Chicago
m*1
12 楼
比wiki上的还要难一点。因为需要分成等长的两个set。 所以还需要一个变量表示set
的长度。P[N/2][n][n/2] 三维dp?
的长度。P[N/2][n][n/2] 三维dp?
A*e
13 楼
评述快上
【在 m****i 的大作中提到】
: @Chicago
【在 m****i 的大作中提到】
: @Chicago
w*a
14 楼
好吧 他可能就是子集的意思，不然就只有一种情况了
C9
15 楼
谢谢安哥，我从了
【在 A*****e 的大作中提到】
: 评述快上
【在 A*****e 的大作中提到】
: 评述快上
m*k
16 楼
猜想：
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
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
c*d
17 楼
恩，您老上吧，要把握好机会啊
【在 C9 的大作中提到】
: 美眉，让我应征一个吧
【在 C9 的大作中提到】
: 美眉，让我应征一个吧
a*m
18 楼
赞！
【在 r**a 的大作中提到】
: 不可能，这是个NPHard问题 http://en.wikipedia.org/wiki/Partition_problem
: 有伪多项式的算法（复杂度和值的范围有关），如果面试官要纯多项式的算法，就喷他
: 一脸
【在 r**a 的大作中提到】
: 不可能，这是个NPHard问题 http://en.wikipedia.org/wiki/Partition_problem
: 有伪多项式的算法（复杂度和值的范围有关），如果面试官要纯多项式的算法，就喷他
: 一脸
e*5
19 楼
A cup?
【在 m****i 的大作中提到】
: @Chicago
【在 m****i 的大作中提到】
: @Chicago
a*m
20 楼
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
【在 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
m*i
21 楼
AAA
【在 e******5 的大作中提到】
: A cup?
【在 e******5 的大作中提到】
: A cup?
h*c
22 楼
假设平衡没有打破
再进来两个数，调整
可能近似
能不能用数学归纳法证明
或者反例
再进来两个数，调整
可能近似
能不能用数学归纳法证明
或者反例
m*i
23 楼
不行，我要会玩的（爱旅游，爱动物，爱台球，etc）
【在 C9 的大作中提到】
: 谢谢安哥，我从了
【在 C9 的大作中提到】
: 谢谢安哥，我从了
h*c
24 楼
如果每次调整都是 log n，那在数学上就是一件很美的事情
a*g
25 楼
这是A++？
【在 m****i 的大作中提到】
: AAA
【在 m****i 的大作中提到】
: AAA
h*c
26 楼
找距离最近的两个
再找下两个
再找下两个
a*g
27 楼
快抢啊。。。
【在 m****i 的大作中提到】
: @Chicago
【在 m****i 的大作中提到】
: @Chicago
i*e
28 楼
赞喷他一脸。
【在 r**a 的大作中提到】
: 不可能，这是个NPHard问题 http://en.wikipedia.org/wiki/Partition_problem
: 有伪多项式的算法（复杂度和值的范围有关），如果面试官要纯多项式的算法，就喷他
: 一脸
【在 r**a 的大作中提到】
: 不可能，这是个NPHard问题 http://en.wikipedia.org/wiki/Partition_problem
: 有伪多项式的算法（复杂度和值的范围有关），如果面试官要纯多项式的算法，就喷他
: 一脸
C9
29 楼
我爱台球啊。花500块买的二手台球桌，经常练。
【在 m****i 的大作中提到】
: 不行，我要会玩的（爱旅游，爱动物，爱台球，etc）
【在 m****i 的大作中提到】
: 不行，我要会玩的（爱旅游，爱动物，爱台球，etc）
h*c
30 楼
没太看懂polynomial 和big O 啥关系
c*d
31 楼
你咋知道平书不会玩涅
【在 m****i 的大作中提到】
: 不行，我要会玩的（爱旅游，爱动物，爱台球，etc）
【在 m****i 的大作中提到】
: 不行，我要会玩的（爱旅游，爱动物，爱台球，etc）
x*9
32 楼
小数据用背包
大数据上集群吧就。。。（逗
==
顺便围观roba大神
大数据上集群吧就。。。（逗
==
顺便围观roba大神
A*e
33 楼
快奔旅游照，宠物照，台球照
【在 C9 的大作中提到】
: 我爱台球啊。花500块买的二手台球桌，经常练。
【在 C9 的大作中提到】
: 我爱台球啊。花500块买的二手台球桌，经常练。
B*4
34 楼
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 啥关系
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 啥关系
m*i
35 楼
上面第二张是在日本，宠物见头像，台球无照，但是PK个把小男生不是问题
【在 A*****e 的大作中提到】
: 快奔旅游照，宠物照，台球照
【在 A*****e 的大作中提到】
: 快奔旅游照，宠物照，台球照
a*2
36 楼
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
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
s*d
37 楼
lz没诚意啊。。啥都没写。。pp也不知道真假。
c*d
38 楼
平书马上拿照片跟你的match...你们在芝加哥pk台球吧，我老围观。。。
【在 m****i 的大作中提到】
: 上面第二张是在日本，宠物见头像，台球无照，但是PK个把小男生不是问题
【在 m****i 的大作中提到】
: 上面第二张是在日本，宠物见头像，台球无照，但是PK个把小男生不是问题
m*i
39 楼
呵呵，你不相信就算了，版大可以做我证人。写再多有意义么？最后不都是看长相，看我顺眼的
，我怎么样都觉
得好，看我不顺眼的，我对他好到天上也不稀罕。
【在 s*******d 的大作中提到】
: lz没诚意啊。。啥都没写。。pp也不知道真假。
，我怎么样都觉
得好，看我不顺眼的，我对他好到天上也不稀罕。
【在 s*******d 的大作中提到】
: lz没诚意啊。。啥都没写。。pp也不知道真假。
w*a
40 楼
美女啊，鹊版可以排前20名
T*e
41 楼
你还用征？
不信
【在 m****i 的大作中提到】
: @Chicago
不信
【在 m****i 的大作中提到】
: @Chicago
m*i
42 楼
这世界天天都是不可信的事情，我不想再纠结了，就是这样。
【在 T*********e 的大作中提到】
: 你还用征？
: 不信
【在 T*********e 的大作中提到】
: 你还用征？
: 不信
x*g
43 楼
美啊
【在 m****i 的大作中提到】
: @Chicago
【在 m****i 的大作中提到】
: @Chicago
m*i
44 楼
谢谢，我最近自信心快要到冰点了
【在 x*********g 的大作中提到】
: 美啊
【在 x*********g 的大作中提到】
: 美啊
T*e
45 楼
你在这里征，只不过是想告诉你自己，你已经走出过去了
至于是否诚信征，赫赫
【在 m****i 的大作中提到】
: 这世界天天都是不可信的事情，我不想再纠结了，就是这样。
至于是否诚信征，赫赫
【在 m****i 的大作中提到】
: 这世界天天都是不可信的事情，我不想再纠结了，就是这样。
相关阅读