PKU1014-Dividing

題目：http://poj.org/problem?id=1014
有總計不超過20000顆大理石，價值1的有a1顆、價值2的有a2顆…一直到價值6
每顆大理石都不能分割，
問是否存在一種方案能把石頭平分給兩人，使其總價值相等？


程式碼：http://codepad.org/xBckZHSn
(做到這樣的題目非常高興...因為這讓我發現原來我不會多重背包優化!!)

最大的總價值是20000*6=120000(最大可能的背包容量)
加上它看起來背包背包的，那麼我們試試看DP：
定義f(n,m)代表前n種石頭，能否湊出價值是m的堆、f(0,0)=true

f(i,j) |= f(i-1,j-k*v[i]) <for all k=0...ai>
N是總石頭數、V是背包容量，時間複雜度就是O(VN)，非常快樂的爆炸了！！！

實在太崩潰了…

怎麼辦呢？

趕快把dd_engi牛的背包問題九講請出來，複習一下第三章：多重背包問題

試考慮價值3的石頭，有13顆(a3=13)
我們原本的程序就好比把價值3變成"一組"互斥的物品，(利用for安排的順序)
它們的價值分別是：3,6,9,12,...,39
跑起來的過程會是像這樣的：
請問f(2,0)是true嗎？是，基於f(2+1,0+3)轉移，把f(3,3)填true
請問f(2,1)是true嗎？是，基於f(2+1,0+3)轉移，把f(3,4)填true
請問f(2,2)是true嗎？是，基於f(2+1,0+3)轉移，把f(3,5)填true
請問f(2,3)是true嗎？是，基於f(2+1,0+3)轉移，把f(3,6)填true
請問f(2,4)是true嗎？是，基於f(2+1,0+3)轉移，把f(3,7)填true
請問f(2,5)是true嗎？是，基於f(2+1,0+3)轉移，把f(3,8)填true
請問f(2,6)是true嗎？是，基於f(2+1,0+3)轉移，把f(3,9)填true

請問f(2,0)是true嗎？是，基於f(2+1,0+6)轉移，把f(3,6)填true
請問f(2,1)是true嗎？是，基於f(2+1,0+6)轉移，把f(3,7)填true
請問f(2,2)是true嗎？是，基於f(2+1,0+6)轉移，把f(3,8)填true
請問f(2,3)是true嗎？是，基於f(2+1,0+6)轉移，把f(3,9)填true
請問f(2,4)是true嗎？是，基於f(2+1,0+6)轉移，把f(3,10)填true
請問f(2,5)是true嗎？是，基於f(2+1,0+6)轉移，把f(3,11)填true
請問f(2,6)是true嗎？是，基於f(2+1,0+6)轉移，把f(3,12)填true
.
.
.
.
請問f(2,0)是true嗎？是，基於f(2+1,0+39)轉移，把f(3,39)填true

請問f(2,1)是true嗎？是，基於f(2+1,0+39)轉移，把f(3,40)填true
請問f(2,2)是true嗎？是，基於f(2+1,0+39)轉移，把f(3,41)填true
請問f(2,3)是true嗎？是，基於f(2+1,0+39)轉移，把f(3,42)填true
請問f(2,4)是true嗎？是，基於f(2+1,0+39)轉移，把f(3,43)填true
請問f(2,5)是true嗎？是，基於f(2+1,0+39)轉移，把f(3,44)填true
請問f(2,6)是true嗎？是，基於f(2+1,0+39)轉移，把f(3,45)填true

做了非常多不必要的事情！(浪費了好多篇幅.....XDD)

因為上述的做法，總共可能要放13個石頭，
循序問1...13的過程中重複了3+3=6、6+6=12、6+3=9這些事！
(也就是2顆石頭試了2、1+1，4顆石頭則會把4、1+3、2+2等方法全跑一遍)

那麼有沒有一種有效率的系統能表示加總會是1,2,3,...,13的數呢？
走到這裡我們發現，二進制派上用場了！
把13顆石頭分解成四樣物品做01背包：1,2,4,6，
如此一來就能造出3=1+2、5=2+3、7=3+4、...等一直到13
而且最大的情形：1+2+4+6，恰好就是13，不會超過
(聰明的你也能發現，儘管已經二進位化，還是會重複做4+4和2+6，
但是全局要做的事情卻大大的減少了！)

於是最壞的情況(20000顆石頭平均分給六種價值)時間複雜度就是O(V*lg(N/6))
成功將整個執行指令數壓到千萬級以內(12*120000=1440000)，圓滿AC