淺談數(shù)據(jù)的合理組織-文庫吧
2025-06-15 06:12 本頁面
【正文】 題條件特殊性的算法2，一個對象的取值可能達到N的組合級別，所以我們大可放棄對于算法2的討論。我們是否有合理的組織數(shù)據(jù)的辦法呢？【數(shù)據(jù)組織方案三】重新安排這些物品的順序，使得每個附件都緊跟其主件，保證其左邊的第一個主件就是它附屬的主件。如下圖：這樣做的好處是：一個附件能被購買的必要條件就是在其前面的最近的主件被購買了。看似和原來的條件沒有什么變化，但是實際上我們給節(jié)點的位置已經(jīng)加上了一個限制。原本樹上的問題經(jīng)過我們“合理地組織數(shù)據(jù)以后”，成功地轉(zhuǎn)化成了一個序列上的問題。【算法3】這樣組織數(shù)據(jù)以后，我們利用前面提到的條件“一個附件能被購買的必要條件是其前面的最近的主件被購買了”，可以輕松地設(shè)計動態(tài)規(guī)劃算法：定義：cost[i]表示第i個物品的價格weight[i]表示第i個物品的權(quán)值F[i][j][k]表示從第i個物品到第n個物品，最多花費j元，第i個物品前的主件有(k=1)沒有(k=0)被購買。分情況進行狀態(tài)轉(zhuǎn)移：情況I：第i個物品是主件F[i][j][k]=Max{F[i+1][jcost[i]][1]+weight[i] (j=cost[i]),F[i+1][j][0]}情況II：第i個物品是附件 如果k=1 F[i][j][k]= Max{F[i+1][jcost[i]][1]+weight[i] (j=cost[i]),F[i+1][j][1]} 如果k=0 F[i][j][k]= F[i+1][j][0]狀態(tài)總數(shù)：O(NM)轉(zhuǎn)移代價：O(1)時間復雜度同樣是O(NM)。很郁悶的金明【題意描述】給出N個物品，可以直接被購買的稱為主件，而不能直接被購買的稱為附件，附件只有當其主件被購買了才能被購買，一個主件可以有任意多個附件，附件可以有多級，也就是說如果某個物品是附件，那么它還有可能有附屬于它的下一級附件。每個物品都有一個權(quán)值(50000)。任務 購買一些物品，總價格不超過M，使得被購買的物品的權(quán)值之和最大。N60M3200【問題分析】現(xiàn)在題目在原題的基礎(chǔ)上不僅放寬了附件的個數(shù)，還放寬了附件的層數(shù)，如圖所示：從上圖中，我們可以對本題有一個感性的認識：關(guān)系又“寬”又“深”。我們依然試著從前面的題目中尋找算法：我們可以直接套用算法1，因為該算法正好將數(shù)據(jù)作為樹結(jié)構(gòu)來進行處理。而利用了題目特殊條件的算法2和算法3，直接套用算法肯定是行不通的。但是他們都很有啟發(fā)性：拋棄樹形的結(jié)構(gòu)，重新組織成線形?，F(xiàn)在的題目是不是也可以類似解決呢？【組織數(shù)據(jù)方案四】算法3相對來說比較算法2更加一般，所以現(xiàn)在我們再回過頭來研究一下算法3，希望在分析過程中找到一些靈感?；貞浰惴?的思路：把同在一個組的主件放在附件的前面，利用動態(tài)規(guī)劃“加一維”的思想，順利地實現(xiàn)了將問題轉(zhuǎn)化到序列上來。關(guān)鍵字：主件在前 序列 動態(tài)規(guī)劃我們聯(lián)想到利用樹的先根遍歷序，而且正好滿足上面的關(guān)系。但是這樣有什么好處嗎？還能進行動態(tài)規(guī)劃嗎？怎樣設(shè)計狀態(tài)才能傳遞父節(jié)點的狀態(tài)呢？我們再回過去看算法3的狀態(tài)轉(zhuǎn)移：假設(shè)當前狀態(tài)是F[i][j][k]，且k=0。如果i是附件，那么實際上在到達下一個主件以前，i后面的附件是都不會被購買的。上圖中，對于附件a，實際上一個k=0的狀態(tài)傳遞下去是沒有意義的，因為附件b和附件c也必然不能被購買。思考并總結(jié)上面的結(jié)論：對于一個主件，我們?nèi)绻毁徺I的話，那么其附件我們都不用考慮，而直接“跳”到下一個主件。我們把它應用到本題中來：重要結(jié)論 我們考慮一棵子樹的時候，如果我們不購買其根節(jié)點，那么其子樹中所有節(jié)點我們都不必討論了。這一結(jié)論似乎很顯然，但是我們并不是要在樹結(jié)構(gòu)中用這一結(jié)論。正如上面提到的，我們要在樹的先根遍序上進行動態(tài)規(guī)劃，而這一結(jié)論正是我們成功的關(guān)鍵?！舅惴?】根據(jù)前面的思考，我們先依次求出每棵樹的先根遍歷序，并保存在同一個序列l(wèi)ist[]中。為了利用上面的結(jié)論，我們還要求出以節(jié)點i為根的子樹的節(jié)點總數(shù)count[i]?，F(xiàn)在我們來設(shè)計動態(tài)規(guī)劃算法：定義：cost[i]表示第i個物品的價格weight[i]表示第i個物品的權(quán)值F[i][j]表示從第i個物品到第n個物品，最多花費j元，能得到的最大權(quán)值和。狀態(tài)轉(zhuǎn)移：對于一個節(jié)點，我們考慮是否購買它：購買：那么我們繼續(xù)考慮它后面的節(jié)點不購買：那么我們跳過它的子孫節(jié)點方程如下：F[i][j]=Max{F[i+1][jcost[list[i]]]+weight[list[i]],F[i+count[list[i]]][j]}這個算法依然是O(NM)的，很完美地解決了本題。并且，這個算法模型對于以前有很多類似的樹形動態(tài)規(guī)劃題目都適用，這是我們在分析本題的過程中的意外收獲?！拘〗Y(jié)】這是一道很有啟發(fā)性的道目。反思這一題的幾個不同難度的版本，不難發(fā)現(xiàn)我們最終都用線形模型上的動態(tài)規(guī)劃取代了容易想到的樹形動態(tài)規(guī)劃算法。我們再次分析前面的算法，試圖發(fā)現(xiàn)其中內(nèi)在的一些東西。其實我們這個題主要就是對于樹形結(jié)構(gòu)和線形結(jié)構(gòu)的選擇，所以我們對比算法4和算法1:不難發(fā)現(xiàn)，相比算法4，算法1其實多出的操作就是枚舉分配給左兒子多少錢。而在線形的序列上，沒有用的錢自然地被分配給后面的元素。也就是說：樹的形態(tài)決定了在狀態(tài)轉(zhuǎn)移的時候要進行額外的枚舉。這正是樹形動態(tài)規(guī)劃算法的瓶頸所在！而我們利用樹的先根遍歷序?qū)⑥D(zhuǎn)樹形
高考資料相關(guān)推薦
鄂ICP備17016276號-1