作者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
→ taitin:可是題目不是說要把數字乘上+1或-1的加總 02/02 17:37
→ taitin:萬一2k-A等於某個在C[1]~c[m]的數字 02/02 17:37
→ taitin:如c=(2,4,6) k=6 02/02 17:42
→ taitin:那切割下來的不就沒辦法相等 02/02 17:42
→ taitin:又若k不等於C裡的數字，那切下來的兩個集合不就多了一個K 02/02 17:43
→ FRAXIS:其實原本問題應該就是Partition Problem 02/02 17:52
→ FRAXIS:上網找應該就有很多資料了.. 02/02 17:52
→ taitin:喔喔~感謝樓上 02/02 23:35