[理工] 演算法問題

[a3813z4813 (johnny110)]

請教一下我遇到的演算法問題

有n個人，體重都是整數

1-1請設計一個演算法把人分成兩堆且兩堆的重量相等(兩堆不用相等)

1-2假設n為偶數，請設計一個演算法把人分成兩堆，兩堆的重量相等且每一堆各為n/2個
人


請問一下要怎麼解呢 卡的有點久...

謝謝！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.137.115.40
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1509279456.A.E08.html
推 FRAXIS: https://en.wikipedia.org/wiki/Partition_problem
推 Xunion: 想借問一下，for迴圈內的if/else那邊，裡面運算都是P(i, j
→ Xunion: )=P(i, j-1)的話為什麼還要用if/else包起來
推 sarsman: if內的是P(i, j-1) or P(i-S[j-1], j-1)
→ sarsman: 這兩個Boolean中有一者為True，P(i, j)即為True
→ a3813z4813: 大致懂了謝謝 ，但請問第二題 ，要怎麼能知道剛好是n/
→ a3813z4813: 2個呢？
→ a3813z4813: 有的解釋是可以把為1的記錄在一個表格裡，然後backtra
→ a3813z4813: cking，但若backtracking到人數不是一半的解這樣就錯
→ a3813z4813: 了
推 FRAXIS: 你要修改 DP 吧 令P(i, j) = 1, if 有一個 size i 的
→ FRAXIS: sorry, P(i, j, k) = 1 if 在前 i 個人中有 一個 size j
→ FRAXIS: 的 subset 其總和為 k