作者ddavid (謊言接線生)
看板Prob_Solve
標題Re: [問題] 烏龜塔問題
時間Fri Mar 8 01:53:24 2019
※ 引述《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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1551981206.A.57E.html
1F：推 nicknick0630: 謝謝大大精闢的解說 03/08 09:45
2F：推 nicknick0630: 那請問大大 可以用通則的方式來證明用重量排序去算 03/08 09:50
3F：→ nicknick0630: 答案會是錯的嗎？ 因為我只會舉範例但想不太到怎麼 03/08 09:50
4F：→ nicknick0630: 證明 03/08 09:50
反例有絕對的命題推翻效果，不需要額外進行推導。
如果是想要推導反例的通則可以自己試看看啦。
5F：推 ckc1ark: 有反例就算是證明了 03/08 10:26
6F：推 cutekid: 推 d 大詳細說明 03/08 11:30
※ 編輯: ddavid (114.36.170.251), 03/09/2019 03:20:52