PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 一個感覺是 dynamic programming 的題目

看板Prob_Solve (計算數學 Problem Solving)作者poao (A Tempo)時間14年前 (2010/04/22 00:31)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串4/12 (看更多)

今天幾個人對於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