作者FRAXIS (喔喔)
看板Grad-ProbAsk
标题Re: [理工] [资结]-交大97-资讯联招-DS&algo核对
时间Tue Feb 2 09:53:23 2010
※ 引述《taitin (小南)》之铭言：
: 8-(1) 若给予一组数据，含有乘+1或-1的资讯
: 则可在O(n)时间内被验证，因此此题目为一npcomplete
给一个不严谨的想法..
假设有一个Subset Sum问题，给定一大小为m整数集合S和一整数K
令S的总和为A, 建立一个阵列C，长度为m+1
C[1] ~ C[m]与S相同 C[m+1] = 2K - A
(所以现在C中的总合是2K)
如果C可以分成两半，使得两部分总和相等的话，那麽Subset Sum就有解了。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.119.162.50
1F：→ taitin:可是题目不是说要把数字乘上+1或-1的加总 02/02 17:37
2F：→ taitin:万一2k-A等於某个在C[1]~c[m]的数字 02/02 17:37
3F：→ taitin:如c=(2,4,6) k=6 02/02 17:42
4F：→ taitin:那切割下来的不就没办法相等 02/02 17:42
5F：→ taitin:又若k不等於C里的数字，那切下来的两个集合不就多了一个K 02/02 17:43
6F：→ FRAXIS:其实原本问题应该就是Partition Problem 02/02 17:52
7F：→ FRAXIS:上网找应该就有很多资料了.. 02/02 17:52
8F：→ taitin:喔喔~感谢楼上 02/02 23:35