推 wheels:洪捷名校攻略秘笈的6-50頁有詳解:) 01/30 22:43
※ 引述《zensword (科)》之銘言：
: http://imageshack.us/photo/my-images/856/47667580.jpg/
: 爬文過了 好像沒有此題的詳解
: 有人比較會解這題嗎？
一些基本的步驟就不列了，只寫最重要的reduce的部分
這個問題可以看成是將C[1]+C[2]+...+C[n]分兩半
乘上+1的數總和會等於乘上-1的數總和(如此才能乘上+1or-1後相加為零)
接著將subset sum轉換成此問題 假設subset sum problem的instance為
set S , integer K , S中所有數總和為T
則我們將T-K+1 , K+1這兩個數加到S裡
此時S中數的總合為T+(T-K+1)+(K+1) = 2T+2 = 2(T+1)
便可用此問題來解之 乘上+1和-1的數總和都會是T+1
接下來看這個解是不是subset sum問題的解
首先剛剛加入的數T-K+1 , K+1不可能會同時乘上+1或-1
若同號則(T-K+1) + (K+1) = T+2 > T+1 超過總和一半
因此S會被分為兩部分 一部分有T-K+1 另一部分有K+1
有T-K+1的部分總和為T+1 (T+1) - (T-K+1) = K
即subset sum問題的解
如果有哪裡錯誤或是不夠嚴謹的地方請告知謝謝~~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.174.3.159