Balance partition Input: give you a integer set {A[0]…A[n-1]}, 0 < A[i] < k, partition to two subsets S1 and S2, minimize |sum(S1)-sum(S2)|

Balance partition
Input: give you a integer set {A[0]…A[n-1]}, 0 < A[i] < k, partition to two subsets S1 and S2, minimize |sum(S1)-sum(S2)|
p(i,j)=1 means there is at least one subset in set i{A[0]…A[i-1]} has sum of j. i is from 0~n-1, j is from 0~(n-1)k
p(i,j)=0 means there is no subset in set i{A[0]…A[i-1]} has sum of j
so
p(i,j) =max{p(i-1,j),p(i-1,j-A[i])}
and define s=sum{A[0]…A[n-1]}/2
so minimize |sum(S1)-sum(S2)|= minimize |s-i:p(i,j)=1|