s******e
发帖数: 108 | 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****x
发帖数: 7404 | 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*****n
发帖数: 188 | 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***u
发帖数: 18 | | C***U
发帖数: 2406 | 5 考虑价值啊。。。那些数就是价值
你要找到N/2个数能够装进Sum(Array)/2，使得装进去的和尽可能大。
【在 J***u 的大作中提到】
: 顶楼上，01背包变种，只不过不考虑价值。
| J***u
发帖数: 18 | 6
啊，刚发现跟背包还是有些不一样的。传统背包里面没要求必须找出几个数，也没对上
限有要求。
【在 C***U 的大作中提到】
: 考虑价值啊。。。那些数就是价值
: 你要找到N/2个数能够装进Sum(Array)/2，使得装进去的和尽可能大。
| s*****n
发帖数: 162 | | p*****2
发帖数: 21240 | 8 按照板上大牛的理论， brute force搞出来就行了吧？
N个数里边选N/2个，使得和最接近sum/2。复杂度
N*(N-1)*(N-2)*(N/2+1) | s*********6
发帖数: 261 | 9 传统01背包本质是个01整数规划问题,在满足一定限制条件下(Volume)最大化目标函数(
Value),好像不是很符合这题的条件啊 | s*********6
发帖数: 261 | 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********u
发帖数: 134 | 11 排序，然后按照顺序每pair每pair的分开放，这样行不？ | s*********6
发帖数: 261 | 12 {1, 4, 9, 16}都通不过
【在 h********u 的大作中提到】
: 排序，然后按照顺序每pair每pair的分开放，这样行不？
| g**e
发帖数: 6127 | 13 又看了一遍，发现作者写这篇文章的时候才高一……
【在 s*****n 的大作中提到】
: 应该是背包的变形题，建议看一下“背包九讲”。
| g**********y
发帖数: 14569 | 14 你再看看，N里面选N/2个不是这个数量级的。
这不是你最喜爱的DP问题，变化了一下。
【在 p*****2 的大作中提到】
: 按照板上大牛的理论， brute force搞出来就行了吧？
: N个数里边选N/2个，使得和最接近sum/2。复杂度
: N*(N-1)*(N-2)*(N/2+1)
| h********u
发帖数: 134 | 15 我没讲清楚，不是直接这样分开放
但是我后来想了一下确实不行
anyway，continue
我记得听说过amazon也问过这题，当时想了一会也没想出来
【在 s*********6 的大作中提到】
: {1, 4, 9, 16}都通不过
| p*****2
发帖数: 21240 | 16
理论上应该N!/((N/2)!*(N/2)!)？ 但是我不清楚怎么写code体现这个复杂度。火鸡帮
讲讲。这个我好像一直没好好想过。
如果暴力写dfs有两种方式，一种是N!/(N/2)!的复杂度，其实大是因为成排列了。另一
个是2^N复杂度了。
【在 g**********y 的大作中提到】
: 你再看看，N里面选N/2个不是这个数量级的。
: 这不是你最喜爱的DP问题，变化了一下。
| p*****2
发帖数: 21240 | 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****a
发帖数: 1212 | 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*****2
发帖数: 21240 | 19
还有一点。一般来说，如果需要显示结果的话，好像dp不是很适用。因为保存中间结果
需要很多内存。板上好像有大牛这么fail的。dfs也许更保险一些？
【在 g**********y 的大作中提到】
: 你再看看，N里面选N/2个不是这个数量级的。
: 这不是你最喜爱的DP问题，变化了一下。
| p*****2
发帖数: 21240 | 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****a
发帖数: 1212 | 21 三个参数
1. 序列长度
2. 目标函数需要贴近的位置，本题中要求两组差值尽量小，所以为0
3. Sum(x)，该值需要均衡到0，因为本题要求两组大小相同
【在 p*****2 的大作中提到】
:
: Y_n(n,0,0) 里边的0,0什么意思？
| p*****2
发帖数: 21240 | 22
多谢。先出去，回来好好学习。
【在 t****a 的大作中提到】
: 三个参数
: 1. 序列长度
: 2. 目标函数需要贴近的位置，本题中要求两组差值尽量小，所以为0
: 3. Sum(x)，该值需要均衡到0，因为本题要求两组大小相同
| g**********y
发帖数: 14569 | 23 N!/(N/2)!^2, 那是指数级的。写dfs也会很大，online比赛里肯定通不过test。
这个跟不限制件数的partition类似，对每个和，你多保存一个件数就行了。从0算到N/
2就可以停。内存跟和的大小相关。
【在 p*****2 的大作中提到】
:
: 多谢。先出去，回来好好学习。
| b***e
发帖数: 1419 | 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**********9
发帖数: 3252 | 25 我好象想到一个最坏是 (Max(x) - Min(x))*N^3的。 | h**********9
发帖数: 3252 | 26
改进了一下变成了：(Max(x) - Min(x))*N*LG(N)
【在 h**********9 的大作中提到】
: 我好象想到一个最坏是 (Max(x) - Min(x))*N^3的。
| b***e
发帖数: 1419 | 27 恭喜你，解决了NP-hard问题。这个值100万。
【在 h**********9 的大作中提到】
:
: 改进了一下变成了：(Max(x) - Min(x))*N*LG(N)
| t****a
发帖数: 1212 | 28 尽是些光说不练的。
拿证明，拿code，拿结果出来，否则浪费大家时间。
【在 b***e 的大作中提到】
: 恭喜你，解决了NP-hard问题。这个值100万。
| h**********9
发帖数: 3252 | 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****y
发帖数: 240 | 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***y
发帖数: 2546 | 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**********9
发帖数: 3252 | 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**********9
发帖数: 3252 | 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****y
发帖数: 240 | 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*********8
发帖数: 45 | 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********t
发帖数: 5706 | 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********t
发帖数: 5706 | 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**********9
发帖数: 3252 | 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****a
发帖数: 1212 | 39 复杂度为O(n^2*s) 其中s为A中元素的和
【在 c********t 的大作中提到】
: 请问这个解法时间，空间复杂度是多少？
| c********t
发帖数: 5706 | 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**********9
发帖数: 3252 | 41
不用管对角线，没什么特别的意思。
1和6置换，或者3和8置换都可以，有时会后多个解。
【在 c********t 的大作中提到】
: 没懂对角线的意思，按你的程序，应该是1和6置换吧
:
: O
: delta递
| c********t
发帖数: 5706 | 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********t
发帖数: 5706 | 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********f
发帖数: 238 | 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******e
发帖数: 108 | 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****x
发帖数: 7404 | 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*****n
发帖数: 188 | 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***u
发帖数: 18 | | C***U
发帖数: 2406 | 49 考虑价值啊。。。那些数就是价值
你要找到N/2个数能够装进Sum(Array)/2，使得装进去的和尽可能大。
【在 J***u 的大作中提到】
: 顶楼上，01背包变种，只不过不考虑价值。
| J***u
发帖数: 18 | 50
啊，刚发现跟背包还是有些不一样的。传统背包里面没要求必须找出几个数，也没对上
限有要求。
【在 C***U 的大作中提到】
: 考虑价值啊。。。那些数就是价值
: 你要找到N/2个数能够装进Sum(Array)/2，使得装进去的和尽可能大。
| | | s*****n
发帖数: 162 | | p*****2
发帖数: 21240 | 52 按照板上大牛的理论， brute force搞出来就行了吧？
N个数里边选N/2个，使得和最接近sum/2。复杂度
N*(N-1)*(N-2)*(N/2+1) | s*********6
发帖数: 261 | 53 传统01背包本质是个01整数规划问题,在满足一定限制条件下(Volume)最大化目标函数(
Value),好像不是很符合这题的条件啊 | s*********6
发帖数: 261 | 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********u
发帖数: 134 | 55 排序，然后按照顺序每pair每pair的分开放，这样行不？ | s*********6
发帖数: 261 | 56 {1, 4, 9, 16}都通不过
【在 h********u 的大作中提到】
: 排序，然后按照顺序每pair每pair的分开放，这样行不？
| g**e
发帖数: 6127 | 57 又看了一遍，发现作者写这篇文章的时候才高一……
【在 s*****n 的大作中提到】
: 应该是背包的变形题，建议看一下“背包九讲”。
| g**********y
发帖数: 14569 | 58 你再看看，N里面选N/2个不是这个数量级的。
这不是你最喜爱的DP问题，变化了一下。
【在 p*****2 的大作中提到】
: 按照板上大牛的理论， brute force搞出来就行了吧？
: N个数里边选N/2个，使得和最接近sum/2。复杂度
: N*(N-1)*(N-2)*(N/2+1)
| h********u
发帖数: 134 | 59 我没讲清楚，不是直接这样分开放
但是我后来想了一下确实不行
anyway，continue
我记得听说过amazon也问过这题，当时想了一会也没想出来
【在 s*********6 的大作中提到】
: {1, 4, 9, 16}都通不过
| p*****2
发帖数: 21240 | 60
理论上应该N!/((N/2)!*(N/2)!)？ 但是我不清楚怎么写code体现这个复杂度。火鸡帮
讲讲。这个我好像一直没好好想过。
如果暴力写dfs有两种方式，一种是N!/(N/2)!的复杂度，其实大是因为成排列了。另一
个是2^N复杂度了。
【在 g**********y 的大作中提到】
: 你再看看，N里面选N/2个不是这个数量级的。
: 这不是你最喜爱的DP问题，变化了一下。
| | | p*****2
发帖数: 21240 | 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****a
发帖数: 1212 | 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*****2
发帖数: 21240 | 63
还有一点。一般来说，如果需要显示结果的话，好像dp不是很适用。因为保存中间结果
需要很多内存。板上好像有大牛这么fail的。dfs也许更保险一些？
【在 g**********y 的大作中提到】
: 你再看看，N里面选N/2个不是这个数量级的。
: 这不是你最喜爱的DP问题，变化了一下。
| p*****2
发帖数: 21240 | 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****a
发帖数: 1212 | 65 三个参数
1. 序列长度
2. 目标函数需要贴近的位置，本题中要求两组差值尽量小，所以为0
3. Sum(x)，该值需要均衡到0，因为本题要求两组大小相同
【在 p*****2 的大作中提到】
:
: Y_n(n,0,0) 里边的0,0什么意思？
| p*****2
发帖数: 21240 | 66
多谢。先出去，回来好好学习。
【在 t****a 的大作中提到】
: 三个参数
: 1. 序列长度
: 2. 目标函数需要贴近的位置，本题中要求两组差值尽量小，所以为0
: 3. Sum(x)，该值需要均衡到0，因为本题要求两组大小相同
| g**********y
发帖数: 14569 | 67 N!/(N/2)!^2, 那是指数级的。写dfs也会很大，online比赛里肯定通不过test。
这个跟不限制件数的partition类似，对每个和，你多保存一个件数就行了。从0算到N/
2就可以停。内存跟和的大小相关。
【在 p*****2 的大作中提到】
:
: 多谢。先出去，回来好好学习。
| b***e
发帖数: 1419 | 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**********9
发帖数: 3252 | 69 我好象想到一个最坏是 (Max(x) - Min(x))*N^3的。 | h**********9
发帖数: 3252 | 70
改进了一下变成了：(Max(x) - Min(x))*N*LG(N)
【在 h**********9 的大作中提到】
: 我好象想到一个最坏是 (Max(x) - Min(x))*N^3的。
| | | b***e
发帖数: 1419 | 71 恭喜你，解决了NP-hard问题。这个值100万。
【在 h**********9 的大作中提到】
:
: 改进了一下变成了：(Max(x) - Min(x))*N*LG(N)
| t****a
发帖数: 1212 | 72 尽是些光说不练的。
拿证明，拿code，拿结果出来，否则浪费大家时间。
【在 b***e 的大作中提到】
: 恭喜你，解决了NP-hard问题。这个值100万。
| h**********9
发帖数: 3252 | 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****y
发帖数: 240 | 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***y
发帖数: 2546 | 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**********9
发帖数: 3252 | 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**********9
发帖数: 3252 | 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****y
发帖数: 240 | 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*********8
发帖数: 45 | 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********t
发帖数: 5706 | 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********t
发帖数: 5706 | 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**********9
发帖数: 3252 | 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****a
发帖数: 1212 | 83 复杂度为O(n^2*s) 其中s为A中元素的和
【在 c********t 的大作中提到】
: 请问这个解法时间，空间复杂度是多少？
| c********t
发帖数: 5706 | 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**********9
发帖数: 3252 | 85
不用管对角线，没什么特别的意思。
1和6置换，或者3和8置换都可以，有时会后多个解。
【在 c********t 的大作中提到】
: 没懂对角线的意思，按你的程序，应该是1和6置换吧
:
: O
: delta递
| c********t
发帖数: 5706 | 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********t
发帖数: 5706 | 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********f
发帖数: 238 | 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**h
发帖数: 893 | 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********m
发帖数: 15480 | 90 每个元素体积相同，volume是n/2就可以了。
数(
【在 s*********6 的大作中提到】
: 传统01背包本质是个01整数规划问题,在满足一定限制条件下(Volume)最大化目标函数(
: Value),好像不是很符合这题的条件啊
| | | a********m
发帖数: 15480 | 91 恩。暴力是c(n/2,n)。
【在 p*****2 的大作中提到】
:
: 多谢。先出去，回来好好学习。
| a********m
发帖数: 15480 | 92 不是npc么？感觉用dp应该可以有o(n^2)解。
【在 b***e 的大作中提到】
: 恭喜你，解决了NP-hard问题。这个值100万。
| f*********m
发帖数: 726 | | f*********m
发帖数: 726 | | b*******e
发帖数: 217 | 95
【在 f*********m 的大作中提到】
: 除了brute force以外的方法
| b*******e
发帖数: 217 | 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*******e
发帖数: 217 | 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*********g
发帖数: 170 | 98 Chevy说的很清楚了：
Balanced Partition
http://people.csail.mit.edu/bdean/6.046/dp/
你只要看i = set.size()/2那一行就可以了。找跟S/2最接近的值。 | b*******e
发帖数: 217 | 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*******e
发帖数: 217 | 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*******e
发帖数: 217 | 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*********g
发帖数: 170 | 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*******e
发帖数: 217 | 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**h
发帖数: 893 | 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********m
发帖数: 15480 | 105 每个元素体积相同，volume是n/2就可以了。
数(
【在 s*********6 的大作中提到】
: 传统01背包本质是个01整数规划问题,在满足一定限制条件下(Volume)最大化目标函数(
: Value),好像不是很符合这题的条件啊
| a********m
发帖数: 15480 | 106 恩。暴力是c(n/2,n)。
【在 p*****2 的大作中提到】
:
: 多谢。先出去，回来好好学习。
| a********m
发帖数: 15480 | 107 不是npc么？感觉用dp应该可以有o(n^2)解。
好像有点问题，还需要再想，求最大和靠近一个值还是有区别。
【在 b***e 的大作中提到】
: 恭喜你，解决了NP-hard问题。这个值100万。
| f*********m
发帖数: 726 | | f*********m
发帖数: 726 | | b*******e
发帖数: 217 | 110
【在 f*********m 的大作中提到】
: 除了brute force以外的方法
| | | b*******e
发帖数: 217 | 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*******e
发帖数: 217 | 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*********g
发帖数: 170 | 113 Chevy说的很清楚了：
Balanced Partition
http://people.csail.mit.edu/bdean/6.046/dp/
你只要看i = set.size()/2那一行就可以了。找跟S/2最接近的值。 | b*******e
发帖数: 217 | 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*******e
发帖数: 217 | 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*******e
发帖数: 217 | 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*********g
发帖数: 170 | 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*******e
发帖数: 217 | 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*********m
发帖数: 726 | 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****1
发帖数: 41 | 120 其实就是这题~
https://www.hackerrank.com/challenges/largest-sum-m
trick就是楼上几位讨论的，三维~ （i,k,s）
从0到第i个数，用里面的k个数组成和为s的可能性为0，或者1.
如果数不会太大可以 保证一定时间内搞完 | | | y***g
发帖数: 1492 | 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*******m
发帖数: 10 | 122 这题，我当初面g的实习生也遇到过，奇怪的是我当时竟然做起来了！！！
可是现在却完全忘记了 |
|
