作者nicknick0630 (NICK)
看板Prob_Solve
標題[問題] 烏龜塔問題
時間Thu Mar 7 23:40:47 2019
烏龜塔問題 :
有 N 隻烏龜，第 i 隻重 Wi 克且有 Si 的力量，代表他可以負載 Si - Wi 的重量在背
上
求由這 N 隻烏龜可以疊出的最大高度?
我所知道的有 2 種解法
其中一種是用動態規劃，解法是 :
先對烏龜用力量由小至大去排序，然後用轉移方程式
dp[i][k] = min{ dp[i-1][k], dp[i][k - 1] + Wi }
去算出答案 ( 當然 dp[i][k-1] + Wi 必須 <= Si 才是合法狀態 )
上面方程式意思是 "從前 i 隻烏龜中，建構 k 層塔的最小重量"
若無法建構 k 層塔則狀態為 invalid
我的問題是
為甚麼要對力量去排序? 而不能用重量去排序再做動態規劃?
我思考過後，對於重量排序我可以找到反例說明他是錯誤的
因為重量大的不一樣要在重量小的下層
舉個例子 :
編號 1 2 3 4
重量 10 20 20 140
力量 60 20 40 150
這樣所可以疊出的最大高度為 2 ( 上到下 : 2 -> 3 )
但其實若是用力量去做排序
編號 1 2 3 4
重量 20 20 10 140
力量 20 40 60 150
這樣所可以疊出的最大高度為 3 ( 上到下 : 1 -> 2 -> 3 )
所以這樣大概可以說明為甚麼重量排序是不對的
因為重量大的可以在上層
那麼我現在所苦惱的就是
為甚麼用力量排序就會是對的?
會不會有個例子是力量小的在上面結果可以讓塔更高呢?
請教各位大大了QQ
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.117.183.79
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1551973250.A.28D.html
1F：推 c910335: 單純好奇你說的兩種解法的另一種是這個嗎 #1BqHom5S03/08 02:39
2F：→ nicknick0630: 對的哦03/08 09:43
8 09:43
4F：→ nicknick0630: 我有文章是說明這個 Moore-Hodgson 演算法和用他解03/08 09:43
5F：→ nicknick0630: 烏龜塔03/08 09:43
※ 編輯: nicknick0630 (101.15.225.66), 03/08/2019 09:44:34
6F：推 cutekid: 大推 Blog ,寫的真好(Y) 03/08 11:24