B*******1
发帖数: 2454 | 1 Is it NP problem ?
How do you partition an array into 2 parts such that the two parts have
equal average?...each partition may contain elements that are non-contiguous
in the array.... |
c*****l
发帖数: 879 | |
B*******1
发帖数: 2454 | 3 Yes. I think Brute force could solve it.
Could we use dp? could not figure out the dp function. |
g**********y
发帖数: 14569 | 4 http://en.wikipedia.org/wiki/Partition_problem
With restriction of number range, this can be solved by DP.
http://people.csail.mit.edu/bdean/6.046/dp/
see "Balanced Partition problem" |
B*******1
发帖数: 2454 | 5 It seems this problem is different from that one. |
S**I
发帖数: 15689 | 6 Do we know whether such a partition exists or not?
contiguous
【在 B*******1 的大作中提到】
: Is it NP problem ?
: How do you partition an array into 2 parts such that the two parts have
: equal average?...each partition may contain elements that are non-contiguous
: in the array....
|
B*******1
发帖数: 2454 | |
S**I
发帖数: 15689 | 8 I think this is a NP problem
【在 B*******1 的大作中提到】
: I think we do not know.
|
r*******g
发帖数: 1335 | 9 原问题和你的不一样。
原问题估计是NP Hard，关键问题是，原问题要求average相等，假设这个average是a，
我们需要不断的找数字他们的average近似是a，比如两个数的和近似是2a，问题关键是
，即使两个数的和不是2a，第三个数依然可能和是3a，所以这个题看不出有什么规律可
循，只能尝试所有情况。
【在 g**********y 的大作中提到】
: http://en.wikipedia.org/wiki/Partition_problem
: With restriction of number range, this can be solved by DP.
: http://people.csail.mit.edu/bdean/6.046/dp/
: see "Balanced Partition problem"
|
B*******1
发帖数: 2454 | 10 But I think we could still use brute force. Is it?
【在 S**I 的大作中提到】
: I think this is a NP problem
|
|
|
B*******1
发帖数: 2454 | 11 刚刚那哥们的帖子怎么删除了，的确刚发现，似乎平均值是跟整个数组的平均值一致的
推导：
a1, a2, a3, a4...an
平均值(a1+a2+...an)/n
假设有这个关系(a1+a2+a3)/3 = (a4+...an)/（n-3)
得出a4 + ... +an = (a1+a2+a3)*(n-3)/3
得出整个数组的和= a1+..a3+a4+..+an = (a1+a2+a3)+ (a1+a2+a3)*(n-3)/3 = (a1+a2
+a3)*n/3
---〉整个数组的和/n = (a1+a2+a3)/3
所以找到的这2个partition的平均值是和整个数组的平均一样的。 |
s**x
发帖数: 405 | 12 Unfortunately this does not prove that this problem is NP complete. It only
shows that an NP complete problem is 'harder' than this problem.
You must reduce an existing NP complete problem (e.g. the Partition problem)
to this problem -- show that a polynomial-time algorithm for this interview
question can be used to solve any instance of the Partition problem. |
c****x
发帖数: 61 | 13 it is not NP, it is an NPH problem
contiguous
【在 B*******1 的大作中提到】
: Is it NP problem ?
: How do you partition an array into 2 parts such that the two parts have
: equal average?...each partition may contain elements that are non-contiguous
: in the array....
|
R****i
发帖数: 104 | 14 也刚刚想到这个问题。
这样可以对这个数组的所有的子集进行比较。
如果平均值是A，那么如果子集的sum ＝ A × NumOfSubset，这就是一个partition。
时间复杂度是O(2^N).
不知道有没有更好的方法？
a2
【在 B*******1 的大作中提到】
: 刚刚那哥们的帖子怎么删除了，的确刚发现，似乎平均值是跟整个数组的平均值一致的
: 推导：
: a1, a2, a3, a4...an
: 平均值(a1+a2+...an)/n
: 假设有这个关系(a1+a2+a3)/3 = (a4+...an)/（n-3)
: 得出a4 + ... +an = (a1+a2+a3)*(n-3)/3
: 得出整个数组的和= a1+..a3+a4+..+an = (a1+a2+a3)+ (a1+a2+a3)*(n-3)/3 = (a1+a2
: +a3)*n/3
: ---〉整个数组的和/n = (a1+a2+a3)/3
: 所以找到的这2个partition的平均值是和整个数组的平均一样的。
|
c*******w
发帖数: 63 | 15 原题只是balanced partition的solution里面的一个特殊情况, 即, 两个partition的
和是相等的,而不是相近的.
所以,仍然可以按照balanced partition找出的结果,然后, check一下,这两个
partition的Sum是不是相等么.
对吗?
【在 r*******g 的大作中提到】
: 原问题和你的不一样。
: 原问题估计是NP Hard，关键问题是，原问题要求average相等，假设这个average是a，
: 我们需要不断的找数字他们的average近似是a，比如两个数的和近似是2a，问题关键是
: ，即使两个数的和不是2a，第三个数依然可能和是3a，所以这个题看不出有什么规律可
: 循，只能尝试所有情况。
|
c********1
发帖数: 52 | 16
Sum相等跟average相等不一样
【在 c*******w 的大作中提到】
: 原题只是balanced partition的solution里面的一个特殊情况, 即, 两个partition的
: 和是相等的,而不是相近的.
: 所以,仍然可以按照balanced partition找出的结果,然后, check一下,这两个
: partition的Sum是不是相等么.
: 对吗?
|
n**********8
发帖数: 188 | 17 可以通过subset sum来证明这个问题是NP-hard：
给定一个subset sum的问题instance：f[1..n]和target_sum，我们可以通过调用avg_
partition的solution来解决这个instance in poly time。方法如下：
1）先假设f中有一个大小为m的subset加起来为target_sum（虽然我们并不知道m是多少
，但我们可以enumerate m = 1..n）
2) 现在给定m，在f的基础上添加3个elements来构造一个新的数组g，然后我们可以证
明把avg_partition的solution在g上run一下，它能找出的解必然和f上subset sum的解
一一对应
2.1)首先加一个数x such that: target_sum/(m+1) 和(SUM(f[1..n])+x-target_sum)
/(n-m+2) 一样大
2.2)其次再加2个数a和b，他们分别为a=10^10*(m+1) 和 b=10^10*(n-m+2)，这里10^
10可以换成任何一个非常大或者非常小的数（这样导致它完全不和f里面的数在同一个
scale，于是必须会被partition开）
3）令g = {f[1],...,f[n],x,a,b}
3.1) 如果avg_partition的solution在g上找到了解，那么这个解的两个partition的
average必然都为10^10+target_sum/(m+1) ，which means 其中一个partition的sum恰
恰是target_sum+a, which means 找到了一个在f上subset sum的解
3.2) 反之，如果存在一个subset的sum是target_sum,那么g必然会有解 |
