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

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

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

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

※ 引述《Franckie ( )》之銘言： : l大的算法有問題 : input: weight{10,20,30} capacity{11,100,10} : l大跑出來的是2, : 但正確的是3 : ※ 引述《Franckie ( )》之銘言： : : 請問l大 2.b 這個步驟您要怎樣實做呢? : : 這個步驟的複雜度應該不太可能是O(1)吧? 我想的是: 1.箱子的capacity必須大於自己"以上"(含自己)的總重量所以在我們的想法裡面的capacity是包含自己重量的capacity 。當然這裡提供一個想法讓這樣的input可以使用l大的演算法，因為我們想的是包含自己重量的 capacity，所以你只要在initialization的時候: for i<-1 to n c[i]<-c[i]+w[i] 一樣可以使用l大的演算法，此步驟其T(n)=O(n)<nlgn不影響整體的複雜度以此題為例原來c={11,100,10},w={10,20,30} 經過調整c={11+10,100+20,10+30} ={21,120,40} 經過sort: c={21,40,120},w={10,30,20} initialization: s[1]={box 1} i=2 s[2]=s[1]+box[2],m[2]=m[1]+1=2 因為c[2]=40>=30+10=w[1]+w[2] i=3 s[3]=s[2]+box[3],m[3]=m[2]+1=3 //偷懶正解，不但求出的長度和正解一樣，結構也相同 2.我getmaxindex()(也就是l大的2b)的時間如果我在每次insertㄧ個 box進入我的解結構的時候，就調整我的max heap是每次花費O(lgn) (因為只要把該box插入last node位置，並且不斷向parent box 進行挑戰和swap,T(n)=O(tree height)=O(lgn) 當我使用getmaxindex()的時候就是delete max操作，調整max heap 一樣也是O(lgn)(將last node放在root，兩個child box取大者和parent box 比較，挑戰成功則swap，一直往下直到leaf或者挑戰失敗,一樣O(lgn)) 調整好以後，再把box[i] insert入heap還是O(lgn), ，而他又在for i<-2 to n的迴圈內，所以最多整個回圈O(nlgn)一樣不影響整體複雜度，因為Sort=O(nlgn) 整個演算法T(n)=O(nlgn) 這裡會讓人搞混的點是說heap sort的時間複雜度本身就是O(nlgn)沒錯，但是若是在每次insert,delete進行操作其實都"每次"都只需要O(lgn) 而非想像中的在for迴圈中又*O(nlgn) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 203.222.23.95 ※ 編輯: keeperkai 來自: 203.222.23.95 (04/23 16:08)