題意: 給定n個人以及他們每個人的體重，要求將這n個人分成兩隊，且兩隊人數差不得超過1個人，且要使得兩個隊伍的體重和相差最小，輸出最後兩隊的體重和。
解法: 從某集合取出子集使得子集的和為某數，是常見的subset sum problem，由於子集合的人數是有限制的，所以遞迴方程要做個小改變。
dp[w] = p=
{ 1, if w = 0
{ dp[w-wi]<<1, if w > 0 and w >= wi, 1 <= i <= n
表示體重和為w時，有哪些可能的人數集合(p狀態壓縮)來形成w。
TAG: DP, subset sum, state compression
注意: 剛開始時就想到DP，只是被lucky cat誤導以為greedy可解，可惡。
沒有留言:
張貼留言
任何意見都樂意傾聽