[理工] 演算法問題

看板Grad-ProbAsk作者 (johnny110)時間8年前 (2017/10/29 20:17), 編輯推噓4(4推 0噓 9→)
留言13則, 4人參與, 8年前最新討論串3/4 (看更多)
請教一下我遇到的演算法問題 有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
推
10/29 20:27, 8年前 , 1F
10/29 20:27, 1F
推
10/30 09:10, 8年前 , 2F
想借問一下，for迴圈內的if/else那邊，裡面運算都是P(i, j
10/30 09:10, 2F
→
10/30 09:10, 8年前 , 3F
)=P(i, j-1)的話為什麼還要用if/else包起來
10/30 09:10, 3F
推
10/30 11:48, 8年前 , 4F
if內的是P(i, j-1) or P(i-S[j-1], j-1)
10/30 11:48, 4F
→
10/30 11:49, 8年前 , 5F
這兩個Boolean中有一者為True，P(i, j)即為True
10/30 11:49, 5F
→
10/30 15:12, 8年前 , 6F
大致懂了謝謝 ，但請問第二題 ，要怎麼能知道剛好是n/
10/30 15:12, 6F
→
10/30 15:12, 8年前 , 7F
2個呢？
10/30 15:12, 7F
→
10/30 15:12, 8年前 , 8F
有的解釋是可以把為1的記錄在一個表格裡，然後backtra
10/30 15:12, 8F
→
10/30 15:12, 8年前 , 9F
cking，但若backtracking到人數不是一半的解這樣就錯
10/30 15:12, 9F
→
10/30 15:12, 8年前 , 10F
了
10/30 15:12, 10F
推
11/05 08:57, 8年前 , 11F
你要修改 DP 吧 令P(i, j) = 1, if 有一個 size i 的
11/05 08:57, 11F
→
11/05 08:58, 8年前 , 12F
sorry, P(i, j, k) = 1 if 在前 i 個人中有 一個 size j
11/05 08:58, 12F
→
11/05 08:59, 8年前 , 13F
的 subset 其總和為 k
11/05 08:59, 13F
‣ 更多 a3813z4813 的文章
文章代碼(AID): #1PzSRWu8 (Grad-ProbAsk)
‣ 更多 a3813z4813 的文章
文章代碼(AID): #1PzSRWu8 (Grad-ProbAsk)