算法合集之淺談數據的合理組織(已修改)
2024-10-28 03:11 本頁面
【正文】 四川省綿陽南山中學 何森 淺談數據的合理組織 引子 題目越來越難 —— 數據關系越來越復雜！ 對組織數據的要求越來越高！ 合理組織在解題中越來越重要！ 【 題意描述 】 給出 N個物品，每個物品都有一個權值 (50000)和一個價格(10000)。我們稱可以直接被購買的物品為主件，稱不能被直接購買的物品為附件，附件只有當其主件被購買了才能被購買，一個主件最多有兩個附件，附件沒有下一級附件。 【 任務 】 用不超過 M元錢，購買一些物品，使得被購買的物品的總權值最大。 金明的預算方案 【 數據規(guī)模 】 N60 M3200 題目中給出的主件與附件間形成樹形結構 ， 而所有的物品間形成森林結構 。 為了方便起見 ， 我們給所有的主件都加上一個 “上級主件 ” ， 這樣 ， 所有的物品形成了一棵樹 。 數據的初步 組織 樹形動態(tài)規(guī)劃算法 ! 算法 1 狀態(tài) F[i][j]表示給以 i為根的子樹，總共花費不超過 j元，所能取得的最大權值和。 ? ? ? 枚舉量太大，效率不高！ 總花費不超過 j 用 左兒子右兄弟表示法 來表示這一棵樹！ 時間復雜度為 O(NM2) 狀態(tài)總數 O(MN) 狀態(tài)轉移代價 O(M) N*M*M=6*108 ，不太理想。 狀態(tài) F[i][j]表示以 i為根的子樹總共花費 j元能獲得的最大權值和。 我們只需要枚舉給左子樹分配多少錢，剩下的錢都分給右子樹。 我們把配套的主件和附件看成一組 。 這樣 ， 顯然對于每一組 ， 可能的購買方案最
教學課件相關推薦
鄂ICP備17016276號-1