[問題] 烏龜塔問題
看板Prob_Solve (計算數學 Problem Solving)作者nicknick0630 (NICK)時間5年前 (2019/03/07 23:40)推噓2(2推 0噓 4→)留言6則, 3人參與討論串1/2 (看更多)
烏龜塔問題 :
有 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://www.ptt.cc/bbs/Prob_Solve/M.1551973250.A.28D.html
推
03/08 02:39,
5年前
, 1F
03/08 02:39, 1F
→
03/08 09:43,
5年前
, 2F
03/08 09:43, 2F
→
03/0, , 3F
03/0, 3F
8 09:43
→
03/08 09:43,
5年前
, 4F
03/08 09:43, 4F
→
03/08 09:43,
5年前
, 5F
03/08 09:43, 5F
※ 編輯: nicknick0630 (101.15.225.66), 03/08/2019 09:44:34
推
03/08 11:24,
5年前
, 6F
03/08 11:24, 6F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
