今天幾個人對於l大的作法討論了一下， 對於該作法的正確性做了一些說明紀錄： 就是對於該作法中， "是否會有另一個解加入現在這隻、拔掉最大值之後變成比最優解更好" 這的點解釋： 也就是說要證明不會存在另外一種堆法，重量和>=最優解但是兩者拔掉最大值、加入烏龜 後變得比最優解更好。 考慮四種情況： a. 最優解的最大值是新加入那隻， 劣解最大值是新加入那隻： 那麼兩者拿掉最大值之後變成原本的最優解 v.s. 劣解 所以一定還是最優解好 b. 最優解的最大值不是新加入那隻， 劣解最大值是新加入那隻： 那麼變成最優解 + Wk - Wmax 重量和會變更小，所以還是最優解好 c. 兩者最大值皆不是新加入那隻： 為方便起見，以下把最優解第i項稱為Ai 劣解第i項稱為Bi i=1 表示烏龜頂 令 j 為 W_Aj > W_Bj 的index且對於所有 1 <= i <= j, 皆有 W_Ai < W_Bi 如果我們把Aj烏龜跟 Bj烏龜交換。 那麼對於所有被疊在Bj之下的烏龜，因為總重量減少了所以都會合法 對於Bj 呢， Bj本來承受了 B1~B(j-1)的烏龜重量， 現在要去承受A1~A(j-1)的重量，但A1之W <= B1之W, A2之W <= B2之W, ... 所以Bj支持的重量也減少了，也絕對合法。 但是這樣交換之後A的總重量減少了，表示原本之最佳解並非最佳，所以矛盾 ※關於一定能找到i 使 Ai之W > Bi之W 之證明： 反證法：假設現在對於所有i, Ai之W皆 <= Bi之W 而不要忘了一開始的假設，假設A和B分別拔掉Wmax之後 B的W和 < A的W和 那麼令A的Wmax在Aj 考慮Bj之W： (1) Bj之W為B裡面W最大的： 兩邊拔掉max之後對所有i, Ai之W皆 <= Bi之W，故 B的W和 >= A的W和 矛盾 (2) Bj之W並非B裡面W最大的： 把Bj 和B裡面Wmax的位置交換，就同(1) d. 最優解的最大值是新加入那隻， 劣解最大值不是： 把兩者最大值拔掉推齊之後變成和c. 一樣之狀況 綜合以上幾點，所以這個作法應當是正確的。 如有表達能力不佳還請見諒... --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.122.45.89