https://en.wikipedia.org/wiki/Partition_problem
https://people.cs.clemson.edu/~bcdean/dp_practice/dp_4.swf
https://gist.github.com/pyemma/ee1a40c51924268e70d0
這個問題是要從一個集合S = {X1, X2, ..., Xn}中，找出兩個子集S1, S2，使得兩者的差異最小，有點像我們去超市時
如果商品要放到2個袋子中，我們希望兩個袋子的重量愈接近愈好
我們會定義P(i, j) = 1 當我們有一群有序的子集1...j相加的總和會等於i，若不存在這樣的子集，則P(i,j) = 0
由這個定義，我們就可以利用dynamic programming來建造我們的table
我們想要知道P(i,j) 是否等於1，可以查看P(i, j-1)是否為1，因為當前面j-1個數字存在這樣的組合
可以得到和為i，那即使再加上當前第j個數字，這條件依然成立
另外一種可能是去查看P(i-Xj, j-1)，因為前j-1個數字，可以得出總和為i - Xj的可能
所以再加上當前的Xj，即可得出總和為i
所以回到我們原本的問題，我們希望找出2個子集，符合下面的式子
Minimize |Sum(S1) - Sum(S2)|
假定S1的總和為i, 則S2的總和，則為Sum(S) - i
所以原本的問題就變成希望找尋到一個子集的總和i，使得(Sum(S) - i) - i為最小
所以可以依照上面wiki的作法，去建一個table，只要找到最後一個可以滿足的i，這就是解
如果i剛好等於原本集合的總和一半，那就表示存在2個子集(有可能有很多種組合)，其各別總和剛好相同
如果是用greedy或differencing algorithm，則會得到suboptimal的解
如果集合很小，直接用brute force也是可以的
留言列表
