d****u
发帖数: 140 | 1 A finite set A of numbers {a1, a2, ...}
find two subsets of A, A1 and A2, and A1 is not the same as A2
denote s1 as the sum of numbers in A1 and so s2
want to minimize |s1 - s2|
I want to prove it as NP-complete, but I couldn't find a suitable NP-
complete problem to reduce to it. Thanks for the hint. | v********e
发帖数: 1058 | 2 I guess you require A1 and A2 to be a partition of A, i.e., A1 \cap A2 = 0,
A_1 + A_2 = A. Otherwise it's a trivial problem.
【在 d****u 的大作中提到】
: A finite set A of numbers {a1, a2, ...}
: find two subsets of A, A1 and A2, and A1 is not the same as A2
: denote s1 as the sum of numbers in A1 and so s2
: want to minimize |s1 - s2|
: I want to prove it as NP-complete, but I couldn't find a suitable NP-
: complete problem to reduce to it. Thanks for the hint.
| s*x
发帖数: 3328 | 3 trivial么？不trivial吧。而且他的那个问题比你说的这个问题还general。比如五个
元素集合1,2,4,7,20。找两个不相等的子集，差最小，怎么trivial的找到一个答案？
,
【在 v********e 的大作中提到】
: I guess you require A1 and A2 to be a partition of A, i.e., A1 \cap A2 = 0,
: A_1 + A_2 = A. Otherwise it's a trivial problem.
| s*x
发帖数: 3328 | 4 按这个样子来看，直觉似乎可以找一个背包问题来做，关键是看背包问题怎么定义方便了
【在 d****u 的大作中提到】
: A finite set A of numbers {a1, a2, ...}
: find two subsets of A, A1 and A2, and A1 is not the same as A2
: denote s1 as the sum of numbers in A1 and so s2
: want to minimize |s1 - s2|
: I want to prove it as NP-complete, but I couldn't find a suitable NP-
: complete problem to reduce to it. Thanks for the hint.
| v********e
发帖数: 1058 | 5 {2}, {1,2}
【在 s*x 的大作中提到】
: trivial么？不trivial吧。而且他的那个问题比你说的这个问题还general。比如五个
: 元素集合1,2,4,7,20。找两个不相等的子集，差最小，怎么trivial的找到一个答案？
:
: ,
| s*x
发帖数: 3328 | 6 不对，1+2+4=7，应该是{1,2,3}和{4}
五个
案？
【在 v********e 的大作中提到】
: {2}, {1,2}
| s*x
发帖数: 3328 | 7 我想出来一个，大概就是对每个背包大小加上一个特别大的数目。比如背包是a,b,c,d,
T那么构造的A包含 a+M,b+M*10,c+M*100,d+M*1000,T+M*1111，这里边M取得充分大，大
概这样。minimize结果要么是0=some abcd - T，要么不是0=some abcd-some abcd
【在 d****u 的大作中提到】
: A finite set A of numbers {a1, a2, ...}
: find two subsets of A, A1 and A2, and A1 is not the same as A2
: denote s1 as the sum of numbers in A1 and so s2
: want to minimize |s1 - s2|
: I want to prove it as NP-complete, but I couldn't find a suitable NP-
: complete problem to reduce to it. Thanks for the hint.
| s*x
发帖数: 3328 | 8 写出paper别忘了致谢我，哈哈
d,
【在 s*x 的大作中提到】
: 我想出来一个，大概就是对每个背包大小加上一个特别大的数目。比如背包是a,b,c,d,
: T那么构造的A包含 a+M,b+M*10,c+M*100,d+M*1000,T+M*1111，这里边M取得充分大，大
: 概这样。minimize结果要么是0=some abcd - T，要么不是0=some abcd-some abcd
| v********e
发帖数: 1058 | 9 i see. i was stupid. say sorry to lz.
【在 s*x 的大作中提到】
: 不对，1+2+4=7，应该是{1,2,3}和{4}
:
: 五个
: 案？
| d****u
发帖数: 140 | 10
谢谢高人
但还是没看出来这两者的对应关系
把背包问题按照你的方法转换后，求得的解怎么再转换回去呢？
【在 s*x 的大作中提到】
: 写出paper别忘了致谢我，哈哈
:
: d,
| | | s*x
发帖数: 3328 | 11 哈哈，不好意思，我前面说的那个好像不对。我是想如果一组中肯定要是一个T的话，
那么最小的就是另外一组的和正好是T，差就是零，对应的正好就是01背包的一个解。
但是那个构造好像有点问题。用 1M+a,10M+b,100M+c,1000M+d,1111M+T，假如 a+d=T，
那么1M+a+1000M+d=1001M+T\neq 1111M+T，不是差为零，看来我一开始想简单了。似乎
你问的这个问题不是很简单阿。
【在 d****u 的大作中提到】
:
: 谢谢高人
: 但还是没看出来这两者的对应关系
: 把背包问题按照你的方法转换后，求得的解怎么再转换回去呢？
| f**f
发帖数: 171 | 12 小X，你觉得{1,2}和{2}这两个集合是{1,2,3}的两个相等的子集么?
不知道楼主的题目是否明确的规定了A1,A2和A的关系：
如果A1+A2是A的一个分割，那就是很典型的2-partition问题，也就是ordinarily NP-
Hard，可以有动态规划的算法解决
个人以为，此题如果A1+A2不是A的分割，那么搜索空间比分割情形下更大了。。。 | f**f
发帖数: 171 | 13 似乎{1,4}和{2,3}更opt，差是0
LOL，假若只要求是不同子集，而不要求是分割
【在 s*x 的大作中提到】
: 不对，1+2+4=7，应该是{1,2,3}和{4}
:
: 五个
: 案？
| d****u
发帖数: 140 | 14 强调一下，对A1和A2没有约束，只要求不相同
分割的话，有现成的证明，用2-partition，as 黄瓜 said
我起初觉得对于这个问题也可以用类似的办法证明NP-complete，没想到介么难
好了，paper写不下去了这回 :( | s*x
发帖数: 3328 | 15 你回帖的时候至少要把贴看全吧，我写的1234是下标，当时顺手就写成下标了，不是实
际的元素。
【在 f**f 的大作中提到】
: 似乎{1,4}和{2,3}更opt，差是0
: LOL，假若只要求是不同子集，而不要求是分割
|
|
