恕刪 其實loco大的解法是正解，用DP只是浪費時間，徒增時間複雜度: 依照loco大的說法是 1.Sort while not finished if 最後一個可以直接加得進去 就加進去 else 調整最佳解的結構，在結構高度相同的前提下，將總重量最佳化 (因為顯然不可能讓他的高度再增加) Q: 1.為何Sort? 因為你把圖畫出來，把每個box含自己的重量加其上box之重量寫出來就會發現， 其實最佳解必定為一個capacity由小->大的sequence 2.為何抽掉最重的box? 所謂抽掉最重的box的意思: (i)Case:第i box重量比考慮前i-1的box的最佳解結構中最重的box還要重， 則我們不變動最佳解(就是抽掉第ibox) (ii)Case:第i box重量比考慮前i-1的box的最佳解結構中最重的box還要輕， 則我們將i-1結構中最重的box抽掉，並且在最後加入第i box(為何 一定加得進去?考慮在i-1最佳解中的最後一個box k之capacity c[k] 以及第i box的capacity c[i],因為c[k]>w[1]+w[2]+...+w[max]+w[k] 其中w[1],w[2]是代表最佳解中的第一個box 第二個box的重量，而 w[max]是其中最大者。又因為w[i]<w[max]且i>k=>c[i]>c[k]>w[1]+w[2] +...+w[max]+...+w[k]>w[1]+w[2]+...+w[i]+...+w[k] 以下為證明在各個階段如此做能夠求得最佳解(高度最高的前提下，重量和最小的 box sequence): i=1 的時候顯然能夠加入第一個box，而此時高度為1的box sequence就是最佳解。 設i=k-1的時候命題成立(假設用以上方法求出的是最佳解:不失一般性設為 x=<box[1],box[2],...,box[s]>,代表在前k-1個箱子中，所有的sequence最高可能 高度為s,且重量是高度為s中最輕的,in other words: w[1],...,w[s]乃最輕的重量總和) i=k的時候 case 加得進去: 則加進去形成length是s+1的最佳解 顯然不可能再形成更長的length不然就和假設自相矛盾,唯一有 可能有問題的是會不會存在一個sequence y+box[k] 和考慮k-1箱子之最佳解x=<box[1],box[2],...,box[s]>+box[k] 不全相同，長度相同且重量和較輕。 顯然如果存在的話y和原來sequence x的長度相同且y重量較輕， 就又和歸納假設矛盾。所以在此case命題成立(在此 狀況下依照上面的方法會求到重量最輕且長度最長的box sequece) case 加不進去:(c[k]<weight(x)+w[k]) subcase:若是w[k]<w[max]，依照方法會把box[max]丟掉，將box[k] 放在最下==>此法求出的box sequence z=<box[1],box[2], ...,box[s],box[k]> 驗證長度: [矛盾]:假設用此法求出的解長度不是最長的合法sequence 代表存在一個合法sequence y其長度>=s+1(因為z長=x長=s) ==>若y中無box[k]，則顯然和歸納假設矛盾 若y中有box[k]，則存在y'=y-box[k],y中只含有前面k-1的 箱子，且y'長度=y長度-1=s+1-1=s=x長度，且y'也合法 ==>y'合法:c[k]>=weight(y')+w[k],又我們在加不進去的 狀況下所以，c[k]<weight(x)+w[k] ==>weight(y')<=c[k]-w[k]<weight(x)，這個和我們的歸納假 設x是考慮到box k-1中重量最小者矛盾，所以長度 必定<=s，長度成立 驗證重量: [矛盾]假設weight(z)不是長度s中重量最小的sequence ==>存在一條y使得weight(y)<weight(z)，且y長=z長=s ==>1.若是y中無box[k]，則y是一條只考慮前k-1box且長度為 s的sequence. ==>weight(y)<weight(z)=weight(x)-w[max]+w[k]< weight(x)，和歸納假設矛盾 2.若是y中有box[k]，又y長=s，代表y的sequence是由 x-box[j]+box[k] 任意j=1 to s 形成的 又我們知道z中是將w[max]帶換掉所以存在有j使得 weight(y)=weight(x)-w[j]+w[k]<weight(x)-w[max]+w[k]= weight(z) ==>w[j]>w[max] 矛盾，所以不可能 依照以上兩點在此subcase中使用此方法會求得最佳解 subcase:若是w[k]>=w[max]，此時我們不變動最佳解，也就是說此 方法求出來的解結構z=x 因為加不進去所以顯然長度不可能在更長 因為w[k]比原結構中的重量都大，所以不用考慮box[k] 重量就會是最佳 依照以上，此subcase中，命題成立 以上涵括所有狀況，所以保證induction step成立，by induction 命題成立 所以意思就是，只要我們保證每個階段我們求得的是長度最長的前提下的重量 最小結構，最後求出來的就會是最佳解，而且此方法正確無誤。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 203.222.23.95 ※ 編輯: keeperkai 來自: 203.222.23.95 (04/23 02:03)