今天几个人对於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