Re: [問題] 烏龜塔問題

[ddavid (謊言接線生)]

※ 引述《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
推 nicknick0630: 謝謝大大精闢的解說
推 nicknick0630: 那請問大大 可以用通則的方式來證明用重量排序去算
→ nicknick0630: 答案會是錯的嗎？ 因為我只會舉範例但想不太到怎麼
→ nicknick0630: 證明
    反例有絕對的命題推翻效果，不需要額外進行推導。

    如果是想要推導反例的通則可以自己試看看啦。

推 ckc1ark: 有反例就算是證明了
推 cutekid: 推 d 大詳細說明
※ 編輯: ddavid (114.36.170.251), 03/09/2019 03:20:52