请问G一题 - 未名空间MITBBS历史存档

s*e2012-10-07 07:10

1 楼

Partition a set of numbers into two such that difference between their sum
is minimum, and both sets have equal number of elements.
For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff =
17-13=4.

q*x2012-10-07 07:10

2 楼

感觉np了。

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

: Partition a set of numbers into two such that difference between their sum
: is minimum, and both sets have equal number of elements.
: For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff =
: 17-13=4.

h*n2012-10-07 07:10

3 楼

classic knapsack.
find N/2 numbers to fit in a sum(Array)/2 knapsack.

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

: Partition a set of numbers into two such that difference between their sum
: is minimum, and both sets have equal number of elements.
: For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff =
: 17-13=4.

J*u2012-10-07 07:10

4 楼

顶楼上，01背包变种，只不过不考虑价值。

C*U2012-10-07 07:10

5 楼

考虑价值啊。。。那些数就是价值
你要找到N/2个数能够装进Sum(Array)/2，使得装进去的和尽可能大。

【在 J***u 的大作中提到】

: 顶楼上，01背包变种，只不过不考虑价值。

J*u2012-10-07 07:10

6 楼

啊，刚发现跟背包还是有些不一样的。传统背包里面没要求必须找出几个数，也没对上
限有要求。

【在 C***U 的大作中提到】

: 考虑价值啊。。。那些数就是价值
: 你要找到N/2个数能够装进Sum(Array)/2，使得装进去的和尽可能大。

s*n2012-10-07 07:10

7 楼

应该是背包的变形题，建议看一下“背包九讲”。

p*22012-10-07 07:10

8 楼

按照板上大牛的理论， brute force搞出来就行了吧？
N个数里边选N/2个，使得和最接近sum/2。复杂度
N*(N-1)*(N-2)*(N/2+1)

s*62012-10-07 07:10

9 楼

传统01背包本质是个01整数规划问题,在满足一定限制条件下(Volume)最大化目标函数(
Value),好像不是很符合这题的条件啊

s*62012-10-07 07:10

10 楼

Partition a set of numbers into two such that difference between their sum
is minimum, and both sets have equal number of elements.
先把数组排序,然后最小和最大放入集合A,然后在B,这样不断交替,这样可以吗?

h*u2012-10-07 07:10

11 楼

排序，然后按照顺序每pair每pair的分开放，这样行不？

s*62012-10-07 07:10

12 楼

{1, 4, 9, 16}都通不过

【在 h********u 的大作中提到】

: 排序，然后按照顺序每pair每pair的分开放，这样行不？

g*e2012-10-07 07:10

13 楼

又看了一遍，发现作者写这篇文章的时候才高一……

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

: 应该是背包的变形题，建议看一下“背包九讲”。

g*y2012-10-07 07:10

14 楼

你再看看，N里面选N/2个不是这个数量级的。
这不是你最喜爱的DP问题，变化了一下。

【在 p*****2 的大作中提到】

: 按照板上大牛的理论， brute force搞出来就行了吧？
: N个数里边选N/2个，使得和最接近sum/2。复杂度
: N*(N-1)*(N-2)*(N/2+1)

h*u2012-10-07 07:10

15 楼

我没讲清楚，不是直接这样分开放
但是我后来想了一下确实不行
anyway，continue
我记得听说过amazon也问过这题，当时想了一会也没想出来

【在 s*********6 的大作中提到】

: {1, 4, 9, 16}都通不过

p*22012-10-07 07:10

16 楼

理论上应该N!/((N/2)!*(N/2)!)？但是我不清楚怎么写code体现这个复杂度。火鸡帮
讲讲。这个我好像一直没好好想过。
如果暴力写dfs有两种方式，一种是N!/(N/2)!的复杂度，其实大是因为成排列了。另一
个是2^N复杂度了。

【在 g**********y 的大作中提到】

: 你再看看，N里面选N/2个不是这个数量级的。
: 这不是你最喜爱的DP问题，变化了一下。

p*22012-10-07 07:10

17 楼

DP还没想明白。
如果dp[N][N/2］的话
dp[i][j] = d[i+1][j] or dp[i+1][j-1]+A[i] (选最接近sum/2的）
这样下来dp[0][N/2] 一定是最优解吗？

【在 g**********y 的大作中提到】

: 你再看看，N里面选N/2个不是这个数量级的。
: 这不是你最喜爱的DP问题，变化了一下。

t*a2012-10-07 07:10

18 楼

给了个DP的解法，请各位指教
Define A={a_1, a_2, …, a_n} as the group of number, n is even
Let X={x_1, x_2, …, x_n}, x_i ∈ {-1,1}
Goal: argmin(Y=∑{A*X}), subject to ∑{X}=0
DP formula:
Y = Y_n(n, 0, 0) = min(Y_{n-1, A_n, -1}, Y_{n-1, -A_n, 1})
详细代码参见
http://kangtu.me/~kangtu/study/interview.html#sec-11
原文中的例子结果为 [-4 [[4 9] [1 16]]] ; 差为-4
该平方数列延长到10的结果 [-1 [[1 25 36 49 81] [4 9 16 64 100]]] ; 差为-1
延长到20: [0 [[1 49 81 100 121 144 169 225 256 289] [4 9 16 25 36 64 196 324
361 400]]] ; 差为0

p*22012-10-07 07:10

19 楼

还有一点。一般来说，如果需要显示结果的话，好像dp不是很适用。因为保存中间结果
需要很多内存。板上好像有大牛这么fail的。dfs也许更保险一些？

【在 g**********y 的大作中提到】

: 你再看看，N里面选N/2个不是这个数量级的。
: 这不是你最喜爱的DP问题，变化了一下。

p*22012-10-07 07:10

20 楼

Y_n(n,0,0) 里边的0,0什么意思？

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

: 给了个DP的解法，请各位指教
: Define A={a_1, a_2, …, a_n} as the group of number, n is even
: Let X={x_1, x_2, …, x_n}, x_i ∈ {-1,1}
: Goal: argmin(Y=∑{A*X}), subject to ∑{X}=0
: DP formula:
: Y = Y_n(n, 0, 0) = min(Y_{n-1, A_n, -1}, Y_{n-1, -A_n, 1})
: 详细代码参见
: http://kangtu.me/~kangtu/study/interview.html#sec-11
: 原文中的例子结果为 [-4 [[4 9] [1 16]]] ; 差为-4
: 该平方数列延长到10的结果 [-1 [[1 25 36 49 81] [4 9 16 64 100]]] ; 差为-1

t*a2012-10-07 07:10

21 楼

三个参数
1. 序列长度
2. 目标函数需要贴近的位置，本题中要求两组差值尽量小，所以为0
3. Sum(x)，该值需要均衡到0，因为本题要求两组大小相同

【在 p*****2 的大作中提到】

:
: Y_n(n,0,0) 里边的0,0什么意思？

p*22012-10-07 07:10

22 楼

多谢。先出去，回来好好学习。

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

: 三个参数
: 1. 序列长度
: 2. 目标函数需要贴近的位置，本题中要求两组差值尽量小，所以为0
: 3. Sum(x)，该值需要均衡到0，因为本题要求两组大小相同

g*y2012-10-07 07:10

23 楼

N!/(N/2)!^2, 那是指数级的。写dfs也会很大，online比赛里肯定通不过test。
这个跟不限制件数的partition类似，对每个和，你多保存一个件数就行了。从0算到N/
2就可以停。内存跟和的大小相关。

【在 p*****2 的大作中提到】

:
: 多谢。先出去，回来好好学习。

b*e2012-10-07 07:10

24 楼

This can be reduced to the knapsack problem. Concretely, if there’s a
knapsack problem, we can construct n problems following the pattern of this
problem.
1. add 1 0 to the list;
2. add 2 0s to the list;
…, …
n. add n 0s to the list;
If any of the these n problems has a solution, then there is a solution for
the original knapsack problem.

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

: Partition a set of numbers into two such that difference between their sum
: is minimum, and both sets have equal number of elements.
: For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff =
: 17-13=4.

h*92012-10-07 07:10

25 楼

我好象想到一个最坏是 (Max(x) - Min(x))*N^3的。

h*92012-10-07 07:10

26 楼

改进了一下变成了：(Max(x) - Min(x))*N*LG(N)

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

: 我好象想到一个最坏是 (Max(x) - Min(x))*N^3的。

b*e2012-10-07 07:10

27 楼

恭喜你，解决了NP-hard问题。这个值100万。

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

:
: 改进了一下变成了：(Max(x) - Min(x))*N*LG(N)

t*a2012-10-07 07:10

28 楼

尽是些光说不练的。
拿证明，拿code，拿结果出来，否则浪费大家时间。

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

: 恭喜你，解决了NP-hard问题。这个值100万。

h*92012-10-07 07:10

29 楼

客气点好吗？我又不是全职解题的，拖家带口的有点时间不容易.
还有一些地方没想通，就当这个是 heuristic greedy 解，不一定能算出最优解，先给
个 O((Max(x) - Min(x))*N^2）的 code, 谁能帮忙验证一下？如果可行我再解析O((
Max(x) - Min(x))*N*LG(N))。
import java.util.Arrays;
public class Partition {

public static int getMinDifference(int input[]) {
assert (input.length % 2 == 0) : "Input must have even number of
items.";
Arrays.sort(input);
int x[] = new int[input.length / 2];
int y[] = new int[input.length / 2];
for(int i = 0; i < x.length; i++) {
x[i] = input[2*i];
y[i] = input[2*i + 1];
}
int delta = sum(y) - sum(x);
int d[][] = new int[y.length][x.length];
for(int i = 0; i < y.length; i++) {
for(int j = 0; j < x.length; j++) {
d[i][j] = y[i] - x[j];
}
}
while(true) {
int max_x = -1;
int max_y = -1;
int max = 0;
for(int i = 0; i < y.length; i++) {
for(int j = 0; j < x.length; j++) {
if(d[i][j] > max && d[i][j] <= (delta >> 1)) {
max = d[i][j];
max_x = j;
max_y = i;
// or break out the loops if not too greedy
// i = y.length - 1;
// j = x.length - 1;
}
}
}
if(max > 0) {
delta -= 2*max;
//swap x, y
int temp = y[max_y];
y[max_y] = x[max_x];
x[max_x] = temp;
for(int i = 0; i < y.length; i++) {
d[i][max_x] = y[i] - x[max_x];
}
for(int j = 0; j < x.length; j++) {
d[max_y][j] = y[max_y] - x[j];
}
}
else {
break;
}
}
// for debugging
/*
for(int i = 0; i < y.length; i++) {
for(int j = 0; j < x.length; j++) {
System.out.print(" " + d[i][j]);
}
System.out.println();
}
*/
System.out.println("Sum(Y) - Sum(X) = " + delta);
System.out.print("X:");
for(int i = 0; i < x.length; i++) {
System.out.print(" " + x[i]);
}
System.out.print("\nY:");
for(int i = 0; i < y.length; i++) {
System.out.print(" " + y[i]);
}
System.out.println();
return delta;
}

public static int sum(int x[]) {
int sum = 0;
for(int i = 0; i < x.length; i++) {
sum += x[i];
}
return sum;
}

public static void main(String args[]) {
int input[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 15 };
// int input[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 15, 16, 300 };
System.out.println("Difference: " + getMinDifference(input));
}
}

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

: 尽是些光说不练的。
: 拿证明，拿code，拿结果出来，否则浪费大家时间。

g*y2012-10-07 07:10

30 楼

你这样贴出一坨代码来，不如讲讲你的思路。

((

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

:
: 客气点好吗？我又不是全职解题的，拖家带口的有点时间不容易.
: 还有一些地方没想通，就当这个是 heuristic greedy 解，不一定能算出最优解，先给
: 个 O((Max(x) - Min(x))*N^2）的 code, 谁能帮忙验证一下？如果可行我再解析O((
: Max(x) - Min(x))*N*LG(N))。
: import java.util.Arrays;
: public class Partition {
:
: public static int getMinDifference(int input[]) {
: assert (input.length % 2 == 0) : "Input must have even number of

C*y2012-10-07 07:10

31 楼

Balanced Partition
http://people.csail.mit.edu/bdean/6.046/dp/

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

: Partition a set of numbers into two such that difference between their sum
: is minimum, and both sets have equal number of elements.
: For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff =
: 17-13=4.

h*92012-10-07 07:10

32 楼

好吧，明后天都要早起去别处上班，改天再画个图解释。大致做法是先sort,然后交叉
分成两组X()和Y()，delta = sum(Y) - sum(X), 用 N/2*N/2 的array d[N/2][N/2]记
录 Y(i,j)-X(i,j), 循环，找 d[i][j] > 0 && d[i][j] < delta/2, 如果找到就修正
delta，直到delta不能再减小。

【在 g****y 的大作中提到】

: 你这样贴出一坨代码来，不如讲讲你的思路。
:
: ((

h*92012-10-07 07:10

33 楼

That's a different problem that has no limit on the number of items for each
partition.

【在 C***y 的大作中提到】

: Balanced Partition
: http://people.csail.mit.edu/bdean/6.046/dp/

g*y2012-10-07 07:10

34 楼

dynamic programming solution.
input: array, with all elements greater than or equal to zero.
p[i,j,k]: Ture, if for array[0..i], there exists a subset of length k, whose
sum equals to j; False otherwise
optimal substructure: p[i,j,k] = True if p[i-1,j,k] is True or p[i-1, j-
array[i], k -1] is True
After calculating p, the original problem becomes: for i = len(array)- 1, k
= len(array) / 2, find j such that p[i,j,k]=True and abs(sum - 2 * j) is
minimized.
def balanced_partition_even(array):
n = len(array)
assert n % 2 == 0
assert all([x >= 0 for x in array])
s = sum(array)
half_n = n // 2
p = [[[False for k in range(half_n + 1)] for j in range(s + 1)] for i in
range(n)]
for i in range(n):
p[i][0][0] = True
p[0][array[i]][1] = True
for k in range(1, half_n + 1):
for i in range(n):
for j in range(s + 1):
if i > 0 and p[i - 1][j][k]:
p[i][j][k] = True
elif j > array[i] and p[i - 1][j - array[i]][k - 1]:
p[i][j][k] = True
min_diff = s
for j in range(s + 1):
if p[-1][j][-1]:
diff = abs(s - 2 * j)
if diff < min_diff:
min_diff = diff
return min_diff

k*82012-10-07 07:10

35 楼

this is a classic dp

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

: Partition a set of numbers into two such that difference between their sum
: is minimum, and both sets have equal number of elements.
: For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff =
: 17-13=4.

c*t2012-10-07 07:10

36 楼

这个解很清楚易懂。
能不能优化？
首先 d[i][j]不用考虑计算负数吧
其次既然已经排过序，感觉计算max diff应该不用遍历d[X][Y]，比如第一次最大diff
是d[0][y.length-1]

((

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

:
: That's a different problem that has no limit on the number of items for each
: partition.

c*t2012-10-07 07:10

37 楼

请问这个解法时间，空间复杂度是多少？

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

: 给了个DP的解法，请各位指教
: Define A={a_1, a_2, …, a_n} as the group of number, n is even
: Let X={x_1, x_2, …, x_n}, x_i ∈ {-1,1}
: Goal: argmin(Y=∑{A*X}), subject to ∑{X}=0
: DP formula:
: Y = Y_n(n, 0, 0) = min(Y_{n-1, A_n, -1}, Y_{n-1, -A_n, 1})
: 详细代码参见
: http://kangtu.me/~kangtu/study/interview.html#sec-11
: 原文中的例子结果为 [-4 [[4 9] [1 16]]] ; 差为-4
: 该平方数列延长到10的结果 [-1 [[1 25 36 49 81] [4 9 16 64 100]]] ; 差为-1

h*92012-10-07 07:10

38 楼

diff
如图可看出对角线之和是delta,找到max diff后swap X/Y, 然后重新计算黄色的cell.
上面的code是偷懒，swap X/Y 后没有重新对 X/Y 排序，否则找 max diff 就是小于 O
(NlgN)。
初始化能保证delta < max(input) - min(input), 每次while() loop使得delta递减直
到收敛，最坏是 max(input) - min(input)次，（实际递减速度应快于每次减一，具体
应该和数据的pattern有关，）现在的问题是能否证明这样每次swap一对元素使得delta递
减，最后能不能收敛到理论最小值。
谁有时间就看看这个行不行吧。

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

: 这个解很清楚易懂。
: 能不能优化？
: 首先 d[i][j]不用考虑计算负数吧
: 其次既然已经排过序，感觉计算max diff应该不用遍历d[X][Y]，比如第一次最大diff
: 是d[0][y.length-1]
:
: ((

t*a2012-10-07 07:10

39 楼

复杂度为O(n^2*s) 其中s为A中元素的和

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

: 请问这个解法时间，空间复杂度是多少？

c*t2012-10-07 07:10

40 楼

没懂对角线的意思，按你的程序，应该是1和6置换吧

O
delta递

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

:
: diff
: 如图可看出对角线之和是delta,找到max diff后swap X/Y, 然后重新计算黄色的cell.
: 上面的code是偷懒，swap X/Y 后没有重新对 X/Y 排序，否则找 max diff 就是小于 O
: (NlgN)。
: 初始化能保证delta < max(input) - min(input), 每次while() loop使得delta递减直
: 到收敛，最坏是 max(input) - min(input)次，（实际递减速度应快于每次减一，具体
: 应该和数据的pattern有关，）现在的问题是能否证明这样每次swap一对元素使得delta递
: 减，最后能不能收敛到理论最小值。
: 谁有时间就看看这个行不行吧。

h*92012-10-07 07:10

41 楼

不用管对角线，没什么特别的意思。
1和6置换，或者3和8置换都可以，有时会后多个解。

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

: 没懂对角线的意思，按你的程序，应该是1和6置换吧
:
: O
: delta递

c*t2012-10-07 07:10

42 楼

有木有人能把这个解法改写成java或c++的？

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

: 给了个DP的解法，请各位指教
: Define A={a_1, a_2, …, a_n} as the group of number, n is even
: Let X={x_1, x_2, …, x_n}, x_i ∈ {-1,1}
: Goal: argmin(Y=∑{A*X}), subject to ∑{X}=0
: DP formula:
: Y = Y_n(n, 0, 0) = min(Y_{n-1, A_n, -1}, Y_{n-1, -A_n, 1})
: 详细代码参见
: http://kangtu.me/~kangtu/study/interview.html#sec-11
: 原文中的例子结果为 [-4 [[4 9] [1 16]]] ; 差为-4
: 该平方数列延长到10的结果 [-1 [[1 25 36 49 81] [4 9 16 64 100]]] ; 差为-1

c*t2012-10-07 07:10

43 楼

你的codes里面有个bug,试试 1,4,7,16

whose
k

【在 g****y 的大作中提到】

: dynamic programming solution.
: input: array, with all elements greater than or equal to zero.
: p[i,j,k]: Ture, if for array[0..i], there exists a subset of length k, whose
: sum equals to j; False otherwise
: optimal substructure: p[i,j,k] = True if p[i-1,j,k] is True or p[i-1, j-
: array[i], k -1] is True
: After calculating p, the original problem becomes: for i = len(array)- 1, k
: = len(array) / 2, find j such that p[i,j,k]=True and abs(sum - 2 * j) is
: minimized.
: def balanced_partition_even(array):

m*f2012-10-07 07:10

44 楼

进来学习

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

: Partition a set of numbers into two such that difference between their sum
: is minimum, and both sets have equal number of elements.
: For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff =
: 17-13=4.

s*e2012-10-07 07:10

45 楼

Partition a set of numbers into two such that difference between their sum
is minimum, and both sets have equal number of elements.
For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff =
17-13=4.

q*x2012-10-07 07:10

46 楼

感觉np了。

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

: Partition a set of numbers into two such that difference between their sum
: is minimum, and both sets have equal number of elements.
: For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff =
: 17-13=4.

h*n2012-10-07 07:10

47 楼

classic knapsack.
find N/2 numbers to fit in a sum(Array)/2 knapsack.

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

: Partition a set of numbers into two such that difference between their sum
: is minimum, and both sets have equal number of elements.
: For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff =
: 17-13=4.

J*u2012-10-07 07:10

48 楼

顶楼上，01背包变种，只不过不考虑价值。

C*U2012-10-07 07:10

49 楼

考虑价值啊。。。那些数就是价值
你要找到N/2个数能够装进Sum(Array)/2，使得装进去的和尽可能大。

【在 J***u 的大作中提到】

: 顶楼上，01背包变种，只不过不考虑价值。

J*u2012-10-07 07:10

50 楼

啊，刚发现跟背包还是有些不一样的。传统背包里面没要求必须找出几个数，也没对上
限有要求。

【在 C***U 的大作中提到】

: 考虑价值啊。。。那些数就是价值
: 你要找到N/2个数能够装进Sum(Array)/2，使得装进去的和尽可能大。

s*n2012-10-07 07:10

51 楼

应该是背包的变形题，建议看一下“背包九讲”。

p*22012-10-07 07:10

52 楼

按照板上大牛的理论， brute force搞出来就行了吧？
N个数里边选N/2个，使得和最接近sum/2。复杂度
N*(N-1)*(N-2)*(N/2+1)

s*62012-10-07 07:10

53 楼

传统01背包本质是个01整数规划问题,在满足一定限制条件下(Volume)最大化目标函数(
Value),好像不是很符合这题的条件啊

s*62012-10-07 07:10

54 楼

Partition a set of numbers into two such that difference between their sum
is minimum, and both sets have equal number of elements.
先把数组排序,然后最小和最大放入集合A,然后在B,这样不断交替,这样可以吗?

h*u2012-10-07 07:10

55 楼

排序，然后按照顺序每pair每pair的分开放，这样行不？

s*62012-10-07 07:10

56 楼

{1, 4, 9, 16}都通不过

【在 h********u 的大作中提到】

: 排序，然后按照顺序每pair每pair的分开放，这样行不？

g*e2012-10-07 07:10

57 楼

又看了一遍，发现作者写这篇文章的时候才高一……

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

: 应该是背包的变形题，建议看一下“背包九讲”。

g*y2012-10-07 07:10

58 楼

你再看看，N里面选N/2个不是这个数量级的。
这不是你最喜爱的DP问题，变化了一下。

【在 p*****2 的大作中提到】

: 按照板上大牛的理论， brute force搞出来就行了吧？
: N个数里边选N/2个，使得和最接近sum/2。复杂度
: N*(N-1)*(N-2)*(N/2+1)

h*u2012-10-07 07:10

59 楼

我没讲清楚，不是直接这样分开放
但是我后来想了一下确实不行
anyway，continue
我记得听说过amazon也问过这题，当时想了一会也没想出来

【在 s*********6 的大作中提到】

: {1, 4, 9, 16}都通不过

p*22012-10-07 07:10

60 楼

理论上应该N!/((N/2)!*(N/2)!)？但是我不清楚怎么写code体现这个复杂度。火鸡帮
讲讲。这个我好像一直没好好想过。
如果暴力写dfs有两种方式，一种是N!/(N/2)!的复杂度，其实大是因为成排列了。另一
个是2^N复杂度了。

【在 g**********y 的大作中提到】

: 你再看看，N里面选N/2个不是这个数量级的。
: 这不是你最喜爱的DP问题，变化了一下。

p*22012-10-07 07:10

61 楼

DP还没想明白。
如果dp[N][N/2］的话
dp[i][j] = d[i+1][j] or dp[i+1][j-1]+A[i] (选最接近sum/2的）
这样下来dp[0][N/2] 一定是最优解吗？

【在 g**********y 的大作中提到】

: 你再看看，N里面选N/2个不是这个数量级的。
: 这不是你最喜爱的DP问题，变化了一下。

t*a2012-10-07 07:10

62 楼

给了个DP的解法，请各位指教
Define A={a_1, a_2, …, a_n} as the group of number, n is even
Let X={x_1, x_2, …, x_n}, x_i ∈ {-1,1}
Goal: argmin(Y=∑{A*X}), subject to ∑{X}=0
DP formula:
Y = Y_n(n, 0, 0) = min(Y_{n-1, A_n, -1}, Y_{n-1, -A_n, 1})
详细代码参见
http://kangtu.me/~kangtu/study/interview.html#sec-11
原文中的例子结果为 [-4 [[4 9] [1 16]]] ; 差为-4
该平方数列延长到10的结果 [-1 [[1 25 36 49 81] [4 9 16 64 100]]] ; 差为-1
延长到20: [0 [[1 49 81 100 121 144 169 225 256 289] [4 9 16 25 36 64 196 324
361 400]]] ; 差为0

p*22012-10-07 07:10

63 楼

还有一点。一般来说，如果需要显示结果的话，好像dp不是很适用。因为保存中间结果
需要很多内存。板上好像有大牛这么fail的。dfs也许更保险一些？

【在 g**********y 的大作中提到】

: 你再看看，N里面选N/2个不是这个数量级的。
: 这不是你最喜爱的DP问题，变化了一下。

p*22012-10-07 07:10

64 楼

Y_n(n,0,0) 里边的0,0什么意思？

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

: 给了个DP的解法，请各位指教
: Define A={a_1, a_2, …, a_n} as the group of number, n is even
: Let X={x_1, x_2, …, x_n}, x_i ∈ {-1,1}
: Goal: argmin(Y=∑{A*X}), subject to ∑{X}=0
: DP formula:
: Y = Y_n(n, 0, 0) = min(Y_{n-1, A_n, -1}, Y_{n-1, -A_n, 1})
: 详细代码参见
: http://kangtu.me/~kangtu/study/interview.html#sec-11
: 原文中的例子结果为 [-4 [[4 9] [1 16]]] ; 差为-4
: 该平方数列延长到10的结果 [-1 [[1 25 36 49 81] [4 9 16 64 100]]] ; 差为-1

t*a2012-10-07 07:10

65 楼

三个参数
1. 序列长度
2. 目标函数需要贴近的位置，本题中要求两组差值尽量小，所以为0
3. Sum(x)，该值需要均衡到0，因为本题要求两组大小相同

【在 p*****2 的大作中提到】

:
: Y_n(n,0,0) 里边的0,0什么意思？

p*22012-10-07 07:10

66 楼

多谢。先出去，回来好好学习。

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

: 三个参数
: 1. 序列长度
: 2. 目标函数需要贴近的位置，本题中要求两组差值尽量小，所以为0
: 3. Sum(x)，该值需要均衡到0，因为本题要求两组大小相同

g*y2012-10-07 07:10

67 楼

N!/(N/2)!^2, 那是指数级的。写dfs也会很大，online比赛里肯定通不过test。
这个跟不限制件数的partition类似，对每个和，你多保存一个件数就行了。从0算到N/
2就可以停。内存跟和的大小相关。

【在 p*****2 的大作中提到】

:
: 多谢。先出去，回来好好学习。

b*e2012-10-07 07:10

68 楼

This can be reduced to the knapsack problem. Concretely, if there’s a
knapsack problem, we can construct n problems following the pattern of this
problem.
1. add 1 0 to the list;
2. add 2 0s to the list;
…, …
n. add n 0s to the list;
If any of the these n problems has a solution, then there is a solution for
the original knapsack problem.

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

: Partition a set of numbers into two such that difference between their sum
: is minimum, and both sets have equal number of elements.
: For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff =
: 17-13=4.

h*92012-10-07 07:10

69 楼

我好象想到一个最坏是 (Max(x) - Min(x))*N^3的。

h*92012-10-07 07:10

70 楼

改进了一下变成了：(Max(x) - Min(x))*N*LG(N)

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

: 我好象想到一个最坏是 (Max(x) - Min(x))*N^3的。

b*e2012-10-07 07:10

71 楼

恭喜你，解决了NP-hard问题。这个值100万。

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

:
: 改进了一下变成了：(Max(x) - Min(x))*N*LG(N)

t*a2012-10-07 07:10

72 楼

尽是些光说不练的。
拿证明，拿code，拿结果出来，否则浪费大家时间。

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

: 恭喜你，解决了NP-hard问题。这个值100万。

h*92012-10-07 07:10

73 楼

客气点好吗？我又不是全职解题的，拖家带口的有点时间不容易.
还有一些地方没想通，就当这个是 heuristic greedy 解，不一定能算出最优解，先给
个 O((Max(x) - Min(x))*N^2）的 code, 谁能帮忙验证一下？如果可行我再解析O((
Max(x) - Min(x))*N*LG(N))。
import java.util.Arrays;
public class Partition {

public static int getMinDifference(int input[]) {
assert (input.length % 2 == 0) : "Input must have even number of
items.";
Arrays.sort(input);
int x[] = new int[input.length / 2];
int y[] = new int[input.length / 2];
for(int i = 0; i < x.length; i++) {
x[i] = input[2*i];
y[i] = input[2*i + 1];
}
int delta = sum(y) - sum(x);
int d[][] = new int[y.length][x.length];
for(int i = 0; i < y.length; i++) {
for(int j = 0; j < x.length; j++) {
d[i][j] = y[i] - x[j];
}
}
while(true) {
int max_x = -1;
int max_y = -1;
int max = 0;
for(int i = 0; i < y.length; i++) {
for(int j = 0; j < x.length; j++) {
if(d[i][j] > max && d[i][j] <= (delta >> 1)) {
max = d[i][j];
max_x = j;
max_y = i;
// or break out the loops if not too greedy
// i = y.length - 1;
// j = x.length - 1;
}
}
}
if(max > 0) {
delta -= 2*max;
//swap x, y
int temp = y[max_y];
y[max_y] = x[max_x];
x[max_x] = temp;
for(int i = 0; i < y.length; i++) {
d[i][max_x] = y[i] - x[max_x];
}
for(int j = 0; j < x.length; j++) {
d[max_y][j] = y[max_y] - x[j];
}
}
else {
break;
}
}
// for debugging
/*
for(int i = 0; i < y.length; i++) {
for(int j = 0; j < x.length; j++) {
System.out.print(" " + d[i][j]);
}
System.out.println();
}
*/
System.out.println("Sum(Y) - Sum(X) = " + delta);
System.out.print("X:");
for(int i = 0; i < x.length; i++) {
System.out.print(" " + x[i]);
}
System.out.print("\nY:");
for(int i = 0; i < y.length; i++) {
System.out.print(" " + y[i]);
}
System.out.println();
return delta;
}

public static int sum(int x[]) {
int sum = 0;
for(int i = 0; i < x.length; i++) {
sum += x[i];
}
return sum;
}

public static void main(String args[]) {
int input[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 15 };
// int input[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 15, 16, 300 };
System.out.println("Difference: " + getMinDifference(input));
}
}

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

: 尽是些光说不练的。
: 拿证明，拿code，拿结果出来，否则浪费大家时间。

g*y2012-10-07 07:10

74 楼

你这样贴出一坨代码来，不如讲讲你的思路。

((

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

:
: 客气点好吗？我又不是全职解题的，拖家带口的有点时间不容易.
: 还有一些地方没想通，就当这个是 heuristic greedy 解，不一定能算出最优解，先给
: 个 O((Max(x) - Min(x))*N^2）的 code, 谁能帮忙验证一下？如果可行我再解析O((
: Max(x) - Min(x))*N*LG(N))。
: import java.util.Arrays;
: public class Partition {
:
: public static int getMinDifference(int input[]) {
: assert (input.length % 2 == 0) : "Input must have even number of

C*y2012-10-07 07:10

75 楼

Balanced Partition
http://people.csail.mit.edu/bdean/6.046/dp/

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

: Partition a set of numbers into two such that difference between their sum
: is minimum, and both sets have equal number of elements.
: For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff =
: 17-13=4.

h*92012-10-07 07:10

76 楼

好吧，明后天都要早起去别处上班，改天再画个图解释。大致做法是先sort,然后交叉
分成两组X()和Y()，delta = sum(Y) - sum(X), 用 N/2*N/2 的array d[N/2][N/2]记
录 Y(i,j)-X(i,j), 循环，找 d[i][j] > 0 && d[i][j] < delta/2, 如果找到就修正
delta，直到delta不能再减小。

【在 g****y 的大作中提到】

: 你这样贴出一坨代码来，不如讲讲你的思路。
:
: ((

h*92012-10-07 07:10

77 楼

That's a different problem that has no limit on the number of items for each
partition.

【在 C***y 的大作中提到】

: Balanced Partition
: http://people.csail.mit.edu/bdean/6.046/dp/

g*y2012-10-07 07:10

78 楼

dynamic programming solution.
input: array, with all elements greater than or equal to zero.
p[i,j,k]: Ture, if for array[0..i], there exists a subset of length k, whose
sum equals to j; False otherwise
optimal substructure: p[i,j,k] = True if p[i-1,j,k] is True or p[i-1, j-
array[i], k -1] is True
After calculating p, the original problem becomes: for i = len(array)- 1, k
= len(array) / 2, find j such that p[i,j,k]=True and abs(sum - 2 * j) is
minimized.
def balanced_partition_even(array):
n = len(array)
assert n % 2 == 0
assert all([x >= 0 for x in array])
s = sum(array)
half_n = n // 2
p = [[[False for k in range(half_n + 1)] for j in range(s + 1)] for i in
range(n)]
for i in range(n):
p[i][0][0] = True
p[0][array[i]][1] = True
for k in range(1, half_n + 1):
for i in range(n):
for j in range(s + 1):
if i > 0 and p[i - 1][j][k]:
p[i][j][k] = True
elif j > array[i] and p[i - 1][j - array[i]][k - 1]:
p[i][j][k] = True
min_diff = s
for j in range(s + 1):
if p[-1][j][-1]:
diff = abs(s - 2 * j)
if diff < min_diff:
min_diff = diff
return min_diff

k*82012-10-07 07:10

79 楼

this is a classic dp

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

: Partition a set of numbers into two such that difference between their sum
: is minimum, and both sets have equal number of elements.
: For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff =
: 17-13=4.

c*t2012-10-07 07:10

80 楼

这个解很清楚易懂。
能不能优化？
首先 d[i][j]不用考虑计算负数吧
其次既然已经排过序，感觉计算max diff应该不用遍历d[X][Y]，比如第一次最大diff
是d[0][y.length-1]

((

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

:
: That's a different problem that has no limit on the number of items for each
: partition.

c*t2012-10-07 07:10

81 楼

请问这个解法时间，空间复杂度是多少？

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

: 给了个DP的解法，请各位指教
: Define A={a_1, a_2, …, a_n} as the group of number, n is even
: Let X={x_1, x_2, …, x_n}, x_i ∈ {-1,1}
: Goal: argmin(Y=∑{A*X}), subject to ∑{X}=0
: DP formula:
: Y = Y_n(n, 0, 0) = min(Y_{n-1, A_n, -1}, Y_{n-1, -A_n, 1})
: 详细代码参见
: http://kangtu.me/~kangtu/study/interview.html#sec-11
: 原文中的例子结果为 [-4 [[4 9] [1 16]]] ; 差为-4
: 该平方数列延长到10的结果 [-1 [[1 25 36 49 81] [4 9 16 64 100]]] ; 差为-1

h*92012-10-07 07:10

82 楼

diff
如图可看出对角线之和是delta,找到max diff后swap X/Y, 然后重新计算黄色的cell.
上面的code是偷懒，swap X/Y 后没有重新对 X/Y 排序，否则找 max diff 就是小于 O
(NlgN)。
初始化能保证delta < max(input) - min(input), 每次while() loop使得delta递减直
到收敛，最坏是 max(input) - min(input)次，（实际递减速度应快于每次减一，具体
应该和数据的pattern有关，）现在的问题是能否证明这样每次swap一对元素使得delta递
减，最后能不能收敛到理论最小值。
谁有时间就看看这个行不行吧。

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

: 这个解很清楚易懂。
: 能不能优化？
: 首先 d[i][j]不用考虑计算负数吧
: 其次既然已经排过序，感觉计算max diff应该不用遍历d[X][Y]，比如第一次最大diff
: 是d[0][y.length-1]
:
: ((

t*a2012-10-07 07:10

83 楼

复杂度为O(n^2*s) 其中s为A中元素的和

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

: 请问这个解法时间，空间复杂度是多少？

c*t2012-10-07 07:10

84 楼

没懂对角线的意思，按你的程序，应该是1和6置换吧

O
delta递

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

:
: diff
: 如图可看出对角线之和是delta,找到max diff后swap X/Y, 然后重新计算黄色的cell.
: 上面的code是偷懒，swap X/Y 后没有重新对 X/Y 排序，否则找 max diff 就是小于 O
: (NlgN)。
: 初始化能保证delta < max(input) - min(input), 每次while() loop使得delta递减直
: 到收敛，最坏是 max(input) - min(input)次，（实际递减速度应快于每次减一，具体
: 应该和数据的pattern有关，）现在的问题是能否证明这样每次swap一对元素使得delta递
: 减，最后能不能收敛到理论最小值。
: 谁有时间就看看这个行不行吧。

h*92012-10-07 07:10

85 楼

不用管对角线，没什么特别的意思。
1和6置换，或者3和8置换都可以，有时会后多个解。

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

: 没懂对角线的意思，按你的程序，应该是1和6置换吧
:
: O
: delta递

c*t2012-10-07 07:10

86 楼

有木有人能把这个解法改写成java或c++的？

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

: 给了个DP的解法，请各位指教
: Define A={a_1, a_2, …, a_n} as the group of number, n is even
: Let X={x_1, x_2, …, x_n}, x_i ∈ {-1,1}
: Goal: argmin(Y=∑{A*X}), subject to ∑{X}=0
: DP formula:
: Y = Y_n(n, 0, 0) = min(Y_{n-1, A_n, -1}, Y_{n-1, -A_n, 1})
: 详细代码参见
: http://kangtu.me/~kangtu/study/interview.html#sec-11
: 原文中的例子结果为 [-4 [[4 9] [1 16]]] ; 差为-4
: 该平方数列延长到10的结果 [-1 [[1 25 36 49 81] [4 9 16 64 100]]] ; 差为-1

c*t2012-10-07 07:10

87 楼

你的codes里面有个bug,试试 1,4,7,16

whose
k

【在 g****y 的大作中提到】

: dynamic programming solution.
: input: array, with all elements greater than or equal to zero.
: p[i,j,k]: Ture, if for array[0..i], there exists a subset of length k, whose
: sum equals to j; False otherwise
: optimal substructure: p[i,j,k] = True if p[i-1,j,k] is True or p[i-1, j-
: array[i], k -1] is True
: After calculating p, the original problem becomes: for i = len(array)- 1, k
: = len(array) / 2, find j such that p[i,j,k]=True and abs(sum - 2 * j) is
: minimized.
: def balanced_partition_even(array):

m*f2012-10-07 07:10

88 楼

进来学习

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

: Partition a set of numbers into two such that difference between their sum
: is minimum, and both sets have equal number of elements.
: For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff =
: 17-13=4.

l*h2012-10-07 07:10

89 楼

kao, google的题这么难。
找到一篇类似的内容: two way partition, 但是不要求两个数组一样长
https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=9&cad=rja&ved=
0CHgQFjAI&url=http%3A%2F%2Fweb.cecs.pdx.edu%2F~bart%2Fcs510ai%2Fpapers%
2Fkorf-ckk.pdf&ei=uB_hUOjTBIOziwLy5IHwBA&usg=
AFQjCNFZof7Y5CI5UpnCKgw1Rwqztwi9Yw&bvm=bv.1355534169,d.cGE

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

: Partition a set of numbers into two such that difference between their sum
: is minimum, and both sets have equal number of elements.
: For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff =
: 17-13=4.

a*m2012-10-07 07:10

90 楼

每个元素体积相同，volume是n/2就可以了。

数(

【在 s*********6 的大作中提到】

: 传统01背包本质是个01整数规划问题,在满足一定限制条件下(Volume)最大化目标函数(
: Value),好像不是很符合这题的条件啊

a*m2012-10-07 07:10

91 楼

恩。暴力是c(n/2,n)。

【在 p*****2 的大作中提到】

:
: 多谢。先出去，回来好好学习。

a*m2012-10-07 07:10

92 楼

不是npc么？感觉用dp应该可以有o(n^2)解。

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

: 恭喜你，解决了NP-hard问题。这个值100万。

f*m2012-10-07 07:10

93 楼

这题大家有结论了吗?

f*m2012-10-07 07:10

94 楼

除了brute force以外的方法

b*e2012-10-07 07:10

95 楼

【在 f*********m 的大作中提到】

: 除了brute force以外的方法

b*e2012-10-07 07:10

96 楼

DP problem: knapsack
Recursive formulation:
Exist(i, j, k) = Exist(i-1, j, k) || Exist(i-1, j-Xi, k-1)
Where i is the index of ith element, j is the sum targeted, and k is the
number of elements selected to get the j and Xi is the value of the ith
element.
We need to decide whether any Exist(n, j, n/2) is true for j = X0, X0+1, ...
n/2.
For all j where Exist(n, j, n/2) == true, pick the j which is closest to Sum
(n) / 2. ------(3)
Then, Abs(Sum(n) /2 - j - j) is the smallest delta of the two subsets we can
get.
If we maintain an matrix to track the elements added in set from i= 0, j =
0, k = 0 to i = n, j= the picked j in step (3), and k = n/2, we can get the
set....
Complexity: n * n * sum(n)

b*e2012-10-07 07:10

97 楼

add one more dimentation to that algorithm to track the number of elements.
see my algorithm post earleir.

ved=

【在 l**h 的大作中提到】

: kao, google的题这么难。
: 找到一篇类似的内容: two way partition, 但是不要求两个数组一样长
: https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=9&cad=rja&ved=
: 0CHgQFjAI&url=http%3A%2F%2Fweb.cecs.pdx.edu%2F~bart%2Fcs510ai%2Fpapers%
: 2Fkorf-ckk.pdf&ei=uB_hUOjTBIOziwLy5IHwBA&usg=
: AFQjCNFZof7Y5CI5UpnCKgw1Rwqztwi9Yw&bvm=bv.1355534169,d.cGE

m*g2012-10-07 07:10

98 楼

Chevy说的很清楚了：
Balanced Partition
http://people.csail.mit.edu/bdean/6.046/dp/
你只要看i = set.size()/2那一行就可以了。找跟S/2最接近的值。

b*e2012-10-07 07:10

99 楼

where is i = set.size()/2 那一行 in the link below?
i is the ith element in the algorithm in the link below.
need to introduce a k to track the number of elements...

【在 m*********g 的大作中提到】

: Chevy说的很清楚了：
: Balanced Partition
: http://people.csail.mit.edu/bdean/6.046/dp/
: 你只要看i = set.size()/2那一行就可以了。找跟S/2最接近的值。

b*e2012-10-07 07:10

100 楼

i indicates the first i elements.
so the ith row in the original problem not necessarily give the optimal
solution. need to introduce k to trace the number of elements.
I provied a DP algorithm which is an extension of the balanced partition in
MIT website.
optional soution is related to D(n, sum(n)/2, n/2)

b*e2012-10-07 07:10

101 楼

correct solution...
same to my solution.

whose
k

【在 g****y 的大作中提到】

: dynamic programming solution.
: input: array, with all elements greater than or equal to zero.
: p[i,j,k]: Ture, if for array[0..i], there exists a subset of length k, whose
: sum equals to j; False otherwise
: optimal substructure: p[i,j,k] = True if p[i-1,j,k] is True or p[i-1, j-
: array[i], k -1] is True
: After calculating p, the original problem becomes: for i = len(array)- 1, k
: = len(array) / 2, find j such that p[i,j,k]=True and abs(sum - 2 * j) is
: minimized.
: def balanced_partition_even(array):

m*g2012-10-07 07:10

102 楼

我对i的理解是：
我们建立一个n * sum(a1,...,an)的table。i是集合S中包含的元素的个数。
1. 当i=1时，S1中只有一个元素。我们有p(1,a1） = p(1,a2) = ... = p(1,an) = 1.
2. 当I= 2时，我们有p(2,a1a2) = p(2,a1,a3) = ... = p(2,an-1an) = 1
当i=set.size/2时，其中最接近sum（）/2 的值就是结果。
复杂度是O(n * n * sum(a1,...,an))

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

: where is i = set.size()/2 那一行 in the link below?
: i is the ith element in the algorithm in the link below.
: need to introduce a k to track the number of elements...

b*e2012-10-07 07:10

103 楼

how can you write your recursive function based on the understanding of your
"i".
my i and the i in MIT website is the "ith" element or the "first ith"
elements.

l*h2012-10-07 07:10

104 楼

kao, google的题这么难。
找到一篇类似的内容: two way partition, 但是不要求两个数组一样长
https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=9&cad=rja&ved=
0CHgQFjAI&url=http%3A%2F%2Fweb.cecs.pdx.edu%2F~bart%2Fcs510ai%2Fpapers%
2Fkorf-ckk.pdf&ei=uB_hUOjTBIOziwLy5IHwBA&usg=
AFQjCNFZof7Y5CI5UpnCKgw1Rwqztwi9Yw&bvm=bv.1355534169,d.cGE

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

: Partition a set of numbers into two such that difference between their sum
: is minimum, and both sets have equal number of elements.
: For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff =
: 17-13=4.

a*m2012-10-07 07:10

105 楼

每个元素体积相同，volume是n/2就可以了。

数(

【在 s*********6 的大作中提到】

: 传统01背包本质是个01整数规划问题,在满足一定限制条件下(Volume)最大化目标函数(
: Value),好像不是很符合这题的条件啊

a*m2012-10-07 07:10

106 楼

恩。暴力是c(n/2,n)。

【在 p*****2 的大作中提到】

:
: 多谢。先出去，回来好好学习。

a*m2012-10-07 07:10

107 楼

不是npc么？感觉用dp应该可以有o(n^2)解。
好像有点问题，还需要再想，求最大和靠近一个值还是有区别。

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

: 恭喜你，解决了NP-hard问题。这个值100万。

f*m2012-10-07 07:10

108 楼

这题大家有结论了吗?

f*m2012-10-07 07:10

109 楼

除了brute force以外的方法

b*e2012-10-07 07:10

110 楼

【在 f*********m 的大作中提到】

: 除了brute force以外的方法

b*e2012-10-07 07:10

111 楼

DP problem: knapsack
Recursive formulation:
Exist(i, j, k) = Exist(i-1, j, k) || Exist(i-1, j-Xi, k-1)
Where i is the index of ith element, j is the sum targeted, and k is the
number of elements selected to get the j and Xi is the value of the ith
element.
We need to decide whether any Exist(n, j, n/2) is true for j = X0, X0+1, ...
n/2.
For all j where Exist(n, j, n/2) == true, pick the j which is closest to Sum
(n) / 2. ------(3)
Then, Abs(Sum(n) /2 - j - j) is the smallest delta of the two subsets we can
get.
If we maintain an matrix to track the elements added in set from i= 0, j =
0, k = 0 to i = n, j= the picked j in step (3), and k = n/2, we can get the
set....
Complexity: n * n * sum(n)

b*e2012-10-07 07:10

112 楼

add one more dimentation to that algorithm to track the number of elements.
see my algorithm post earleir.

ved=

【在 l**h 的大作中提到】

: kao, google的题这么难。
: 找到一篇类似的内容: two way partition, 但是不要求两个数组一样长
: https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=9&cad=rja&ved=
: 0CHgQFjAI&url=http%3A%2F%2Fweb.cecs.pdx.edu%2F~bart%2Fcs510ai%2Fpapers%
: 2Fkorf-ckk.pdf&ei=uB_hUOjTBIOziwLy5IHwBA&usg=
: AFQjCNFZof7Y5CI5UpnCKgw1Rwqztwi9Yw&bvm=bv.1355534169,d.cGE

m*g2012-10-07 07:10

113 楼

Chevy说的很清楚了：
Balanced Partition
http://people.csail.mit.edu/bdean/6.046/dp/
你只要看i = set.size()/2那一行就可以了。找跟S/2最接近的值。

b*e2012-10-07 07:10

114 楼

where is i = set.size()/2 那一行 in the link below?
i is the ith element in the algorithm in the link below.
need to introduce a k to track the number of elements...

【在 m*********g 的大作中提到】

: Chevy说的很清楚了：
: Balanced Partition
: http://people.csail.mit.edu/bdean/6.046/dp/
: 你只要看i = set.size()/2那一行就可以了。找跟S/2最接近的值。

b*e2012-10-07 07:10

115 楼

i indicates the first i elements.
so the ith row in the original problem not necessarily give the optimal
solution. need to introduce k to trace the number of elements.
I provied a DP algorithm which is an extension of the balanced partition in
MIT website.
optional soution is related to D(n, sum(n)/2, n/2)

b*e2012-10-07 07:10

116 楼

correct solution...
same to my solution.

whose
k

【在 g****y 的大作中提到】

: dynamic programming solution.
: input: array, with all elements greater than or equal to zero.
: p[i,j,k]: Ture, if for array[0..i], there exists a subset of length k, whose
: sum equals to j; False otherwise
: optimal substructure: p[i,j,k] = True if p[i-1,j,k] is True or p[i-1, j-
: array[i], k -1] is True
: After calculating p, the original problem becomes: for i = len(array)- 1, k
: = len(array) / 2, find j such that p[i,j,k]=True and abs(sum - 2 * j) is
: minimized.
: def balanced_partition_even(array):

m*g2012-10-07 07:10

117 楼

我对i的理解是：
我们建立一个n * sum(a1,...,an)的table。i是集合S中包含的元素的个数。
1. 当i=1时，S1中只有一个元素。我们有p(1,a1） = p(1,a2) = ... = p(1,an) = 1.
2. 当I= 2时，我们有p(2,a1a2) = p(2,a1,a3) = ... = p(2,an-1an) = 1
当i=set.size/2时，其中最接近sum（）/2 的值就是结果。
复杂度是O(n * n * sum(a1,...,an))

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

: where is i = set.size()/2 那一行 in the link below?
: i is the ith element in the algorithm in the link below.
: need to introduce a k to track the number of elements...

b*e2012-10-07 07:10

118 楼

how can you write your recursive function based on the understanding of your
"i".
my i and the i in MIT website is the "ith" element or the "first ith"
elements.

f*m2012-10-07 07:10

119 楼

这个bug可能和下面的初始化有关
for i in range(n):
p[0][array[i]][1] = True
改成
for i in range(n):
p[0][array[i]][1] = array[i] == array[0]；
如何？

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

: 你的codes里面有个bug,试试 1,4,7,16
:
: whose
: k

m*12012-10-07 07:10

120 楼

其实就是这题~
https://www.hackerrank.com/challenges/largest-sum-m
trick就是楼上几位讨论的，三维~ （i,k,s）
从0到第i个数，用里面的k个数组成和为s的可能性为0，或者1.
如果数不会太大可以保证一定时间内搞完

y*g2012-10-07 07:10

121 楼

p(i+1,n)=max(p(i,n-a_1),...,p(i,n-a_N))

your

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

: how can you write your recursive function based on the understanding of your
: "i".
: my i and the i in MIT website is the "ith" element or the "first ith"
: elements.

b*m2012-10-07 07:10

122 楼

这题，我当初面g的实习生也遇到过，奇怪的是我当时竟然做起来了！！！
可是现在却完全忘记了