推 chrisdar:我先去搜尋相關資料 謝謝 關鍵字應該是 狀態空間樹 吧 11/07 18:15
→ DJWS:恩...我講的是動態規劃法 XD 11/07 18:24
→ DJWS:不過我沒有實際寫出來 所以不敢保證我的想法對不對 11/07 18:25
推 Fenikso:排序後不一定能找到最佳解 11/07 18:32
現在有兩根木頭，其左端位置分別為 x1 和 x2。
令 x1 <= x2。
這兩根木頭被人力推動後，木頭左端的相對位置只有兩種情形：
甲、一左一右：交由動態規劃解決。
乙、一右一左：如果這兩根木頭都會推到水裡，那麼這就是浪費力氣的推法。比甲還差。
故排序是可行的，
除非有些木頭不打算推到水裡。
－
補充一下。
上一篇所說的方法是假設有些木頭不必放到水裡。
木頭不必都放入水裡的話，
就我的認知，這樣要用動態規劃解決，仍需指數時間。
如果全部的木頭都要放入水裡，
那麼狀態空間設定成: (池塘寬度,木材數目) 就可以了。
就跟ledia板友所描述的是一樣的。
這樣的問題用動態規劃應可在多項式時間求得。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.137.83.198
推 chrisdar:PS.木頭一定要推到水裡(數學上=彼此區間不重疊) 11/07 19:43
※ 編輯: DJWS 來自: 220.137.83.198 (11/07 20:04)