Re: [問題] 烏龜塔問題
看板Prob_Solve (計算數學 Problem Solving)作者ddavid (謊言接線生)時間5年前 (2019/03/08 01:53)推噓4(4推 0噓 2→)留言6則, 3人參與討論串2/2 (看更多)
※ 引述《nicknick0630 (NICK)》之銘言：
: 烏龜塔問題 :
: 有 N 隻烏龜，第 i 隻重 Wi 克且有 Si 的力量，代表他可以負載 Si - Wi 的重量在背上
: 求由這 N 隻烏龜可以疊出的最大高度?
假設已知正確答案疊出了高度m，由上而下所有重量與力量如下：
重量 W1 W2 ... W(m-1) Wm
力量 S1 S2 ... S(m-1) Sm
考慮其中某一層k，依題意，他的力量能夠撐起包括自己在內的上層所有重量：
Sk >= W1 + W2 + ... + W(k-1) + Wk
假設k這隻事實上比他上一層(k-1)那隻力量還小：
S(k-1) > Sk
得到：
S(k-1) > Sk
>= W1 + W2 + ... + W(k-1) + Wk
發現其實(k-1)這隻也可以抬得動這k層全部的重量。另外：
Sk >= W1 + W2 + ... + W(k-2) + W(k-1) + Wk
> W1 + W2 + ... + W(k-2) + Wk
理所當然地，k當然也抬得動這k層少了(k-1)那隻的重量。
也就是說原本的排序：
1 2 ... (k-1) k ... m
改成：
1 2 ... k (k-1) ... m
也就是這兩層對調也不會有任何問題，k跟(k-1)都還是抬得動。
因此，每當相連的上層比下層有力時，把這兩層對調一定不會發生問題。反覆這
樣的操作，我們必然可以將順序調整成下層比上層有力而仍然不發生問題（可經由泡
沫排序法實際操作得到），因此必然存在一組最佳解是力量可以依序由上而下剛好是
由小到大，而這組解可由力量排序的DP得到。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.36.170.251
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1551981206.A.57E.html
推
03/08 09:45,
5年前
, 1F
03/08 09:45, 1F
推
03/08 09:50,
5年前
, 2F
03/08 09:50, 2F
→
03/08 09:50,
5年前
, 3F
03/08 09:50, 3F
→
03/08 09:50,
5年前
, 4F
03/08 09:50, 4F
反例有絕對的命題推翻效果，不需要額外進行推導。
如果是想要推導反例的通則可以自己試看看啦。
推
03/08 10:26,
5年前
, 5F
03/08 10:26, 5F
推
03/08 11:30,
5年前
, 6F
03/08 11:30, 6F
※ 編輯: ddavid (114.36.170.251), 03/09/2019 03:20:52
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
