Re: [理工] [資結]-交大97-資訊聯招-DS&algo核對

看板Grad-ProbAsk作者 (喔喔)時間16年前 (2010/02/02 09:53), 編輯推噓0(0推 0噓 8→)
留言8則, 2人參與, 最新討論串2/3 (看更多)
※ 引述《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
→
02/02 17:37, , 1F
可是題目不是說要把數字乘上+1或-1的加總
02/02 17:37, 1F
→
02/02 17:37, , 2F
萬一2k-A等於某個在C[1]~c[m]的數字
02/02 17:37, 2F
→
02/02 17:42, , 3F
如c=(2,4,6) k=6
02/02 17:42, 3F
→
02/02 17:42, , 4F
那切割下來的不就沒辦法相等
02/02 17:42, 4F
→
02/02 17:43, , 5F
又若k不等於C裡的數字，那切下來的兩個集合不就多了一個K
02/02 17:43, 5F
→
02/02 17:52, , 6F
其實原本問題應該就是Partition Problem
02/02 17:52, 6F
→
02/02 17:52, , 7F
上網找應該就有很多資料了..
02/02 17:52, 7F
→
02/02 23:35, , 8F
喔喔~感謝樓上
02/02 23:35, 8F
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1BPuMLIA (Grad-ProbAsk)
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1BPuMLIA (Grad-ProbAsk)