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