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

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

看板Prob_Solve (計算數學 Problem Solving)作者keeperkai (keeperkai)時間14年前 (2010/04/23 02:02)推噓1(1推 0噓 1→)

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

恕刪其實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)