PhD毕业后，需要多长时间的工作经验才能参加PE考试 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Environmental - 环境科学与工程

PhD毕业后，需要多长时间的工作经验才能参加PE考试

PhD毕业后，需要多长时间的工作经验才能参加PE考试# Environmental - 环境科学与工程

n*r2008-05-22 07:05

1 楼

给定一个array A, size(A) = n, n is an even number.
Denote Sum(A) = A[0]+A[1]+...+A[n-1]
Split A into A1, A2, size(A1) = size(A2) = n/2,
the goal is to minimize Sum(A1)-Sum(A2).
Is there any efficient algorithms for this problem?

c*n2008-05-22 07:05

2 楼

请知道的大侠帮忙！

n*r2008-05-22 07:05

3 楼

Sorry, the goal is to minimize
abs(Sum(A1)-Sum(A2))

v*n2008-05-22 07:05

4 楼

One year in California.

【在 c********n 的大作中提到】

: 请知道的大侠帮忙！

T*92008-05-22 07:05

5 楼

没看懂啊
是Sum(A1)-Sum(A2)的绝对值么？要不你直接最大的n/2给A2,最小的n/2给A1

【在 n*******r 的大作中提到】

: 给定一个array A, size(A) = n, n is an even number.
: Denote Sum(A) = A[0]+A[1]+...+A[n-1]
: Split A into A1, A2, size(A1) = size(A2) = n/2,
: the goal is to minimize Sum(A1)-Sum(A2).
: Is there any efficient algorithms for this problem?

g*r2008-05-22 07:05

6 楼

depends. go to your state license board to do research..

【在 c********n 的大作中提到】

: 请知道的大侠帮忙！

T*92008-05-22 07:05

7 楼

要是绝对值的话，应该是NPC
干脆recursive得了

【在 T*****9 的大作中提到】

: 没看懂啊
: 是Sum(A1)-Sum(A2)的绝对值么？要不你直接最大的n/2给A2,最小的n/2给A1

b*e2008-05-22 07:05

8 楼

I believe this is NPC. Here is a reduction to Knapsack:
Given a Knapsack problem as follows:
An array A = {a1, ..., an}, where for each i, ai is a positive integer, find
a subset B of A such that sum(B) = v, where v is a positive interger.
Without
losing generality, we can assume v <= sum(A) / 2;
Let w = sum(A) - 2 * v.
Let A' = A union {w} union Z, where Z = {0, ..., 0} is a set that contains n
+1 0s.
Now if your problem can be solved effectively, then I apply that algorithm
on A' to find out

【在 n*******r 的大作中提到】

n*r2008-05-22 07:05

9 楼

Thanks for proving this is a NPC, I will apply heuristic then.

s*h2008-05-22 07:05

10 楼

blaze很牛啊。不过我没看懂

f*y2008-05-22 07:05

11 楼

不止图灵
还有克雷千禧奖

find
n

【在 b***e 的大作中提到】

: I believe this is NPC. Here is a reduction to Knapsack:
: Given a Knapsack problem as follows:
: An array A = {a1, ..., an}, where for each i, ai is a positive integer, find
: a subset B of A such that sum(B) = v, where v is a positive interger.
: Without
: losing generality, we can assume v <= sum(A) / 2;
: Let w = sum(A) - 2 * v.
: Let A' = A union {w} union Z, where Z = {0, ..., 0} is a set that contains n
: +1 0s.
: Now if your problem can be solved effectively, then I apply that algorithm

d*a2008-05-22 07:05

12 楼

why NPC? it's a sub/linear. just sort A first, and let A1=Q1(A),Q4(A) (first
and fourth quarters), and A2=Q2, Q3

【在 n*******r 的大作中提到】

b*e2008-05-22 07:05

13 楼

1000, 999, 5, 4, 3, 2, 1, 0.
Even if you are not smart enough, try not to show your stupidity/ignorance.
I am trying to be nice, but I just can't help.

first

【在 d*****a 的大作中提到】

: why NPC? it's a sub/linear. just sort A first, and let A1=Q1(A),Q4(A) (first
: and fourth quarters), and A2=Q2, Q3

t*t2008-05-22 07:05

14 楼

做人要厚道~~~

.

【在 b***e 的大作中提到】

: 1000, 999, 5, 4, 3, 2, 1, 0.
: Even if you are not smart enough, try not to show your stupidity/ignorance.
: I am trying to be nice, but I just can't help.
:
: first

n*t2008-05-22 07:05

15 楼

所以说别和geek混啊，比他笨的多的人一样可以当你的老板，
你还得点头哈腰的。。。

.

【在 b***e 的大作中提到】

: 1000, 999, 5, 4, 3, 2, 1, 0.
: Even if you are not smart enough, try not to show your stupidity/ignorance.
: I am trying to be nice, but I just can't help.
:
: first

f*k2008-05-22 07:05

16 楼

it's the famous subset sum problem, which is an NPC. search for Karmarkar/
Karp algorithm and its complete tree traversing version.

【在 n*******r 的大作中提到】

: Sorry, the goal is to minimize
: abs(Sum(A1)-Sum(A2))

d*a2008-05-22 07:05

17 楼

我傻，你牛，承教，谢谢。

.

【在 b***e 的大作中提到】

: 1000, 999, 5, 4, 3, 2, 1, 0.
: Even if you are not smart enough, try not to show your stupidity/ignorance.
: I am trying to be nice, but I just can't help.
:
: first