Re: [問題] 如何解 池塘邊的木頭 問題
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間16年前 (2008/11/07 19:28)推噓1(1推 0噓 0→)留言1則, 1人參與討論串7/8 (看更多)
推
11/07 18:15,
11/07 18:15
→
11/07 18:24,
11/07 18:24
→
11/07 18:25,
11/07 18:25
推
11/07 18:32,
11/07 18:32
現在有兩根木頭，其左端位置分別為 x1 和 x2。
令 x1 <= x2。
這兩根木頭被人力推動後，木頭左端的相對位置只有兩種情形：
甲、一左一右：交由動態規劃解決。
乙、一右一左：如果這兩根木頭都會推到水裡，那麼這就是浪費力氣的推法。比甲還差。
故排序是可行的，
除非有些木頭不打算推到水裡。
－
補充一下。
上一篇所說的方法是假設有些木頭不必放到水裡。
木頭不必都放入水裡的話，
就我的認知，這樣要用動態規劃解決，仍需指數時間。
如果全部的木頭都要放入水裡，
那麼狀態空間設定成: (池塘寬度,木材數目) 就可以了。
就跟ledia板友所描述的是一樣的。
這樣的問題用動態規劃應可在多項式時間求得。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.137.83.198
推
11/07 19:43, , 1F
11/07 19:43, 1F
※ 編輯: DJWS 來自: 220.137.83.198 (11/07 20:04)
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
