淺談數(shù)據(jù)的合理組織-wenkub
2023-07-15 06:12:41 本頁面
【正文】 變。其中1=k=5且cost[i][k]=j 狀態(tài)總數(shù)：O(NM)轉(zhuǎn)移代價：O(1)這樣，我們得到了一個時間復(fù)雜度為O(NM)的優(yōu)秀算法。【算法二】cost[i][k]表示分組后第i個對象的第k種購買方案的花費(fèi)。我們回到題目并考慮其特殊性：。left[a]表示a的左兒子right[a]表示a的右兒子f[a][b]=Max{Max{f[left[a]][bleft]+f[right[a]][bcost[a]bleft]}+score[a],f[right[a]][b]}這樣我們可以得到一個理論 參見《算法藝術(shù)與信息學(xué)競賽》貪食的九頭龍中對算法復(fù)雜度的分析復(fù)雜度為O(NM2)的算法，但是對于本題的數(shù)據(jù)范圍來說，這個復(fù)雜度并不太理想。【數(shù)據(jù)組織方案一】假設(shè)我們忽略數(shù)據(jù)的特殊性，單從樹結(jié)構(gòu)考慮，我們?nèi)菀紫氲降囊粋€算法是：給所有主件加上一個“級超主件”，把原來的所有主件都變成“超級主件”的附件，如下圖： (圖2)【算法一】這樣，在這棵樹上，我們可以設(shè)計一個動態(tài)規(guī)劃算法： 定義：cost[a]表示a節(jié)點(diǎn)所代表的物品的價格score[a]表示a節(jié)點(diǎn)所代表的物品的得分狀態(tài)f[a][b]表示以節(jié)點(diǎn)a為根的子樹，總共花費(fèi)不超過b元的最多得分。N3200 M60【簡要分析】我們很容易聯(lián)想到經(jīng)典的動態(tài)規(guī)劃之01背包問題。對數(shù)據(jù)組織的合理化，不僅在我們設(shè)計算法時能起到優(yōu)化程序效率的作用，有時，我們在建立解題模型時，合理地組織數(shù)據(jù)可能給我們提供新的思考角度，從而優(yōu)化解題模型，例一就是這樣的一個例子。我們組織數(shù)據(jù)，主要就是通過從“形式”和“順序”這兩個角度來考慮。目的在于引起讀者對于數(shù)據(jù)的合理組織的關(guān)注，并在今后的解題中能積極并靈活地運(yùn)用這一手段。隨著信息學(xué)的發(fā)展，其題目中的關(guān)系也變得越來越錯宗復(fù)雜，給我們解題帶來困難。對數(shù)據(jù)進(jìn)行合理地組織，正是我們面對上述題目時的一種有效手段。【關(guān)鍵字】組織數(shù)據(jù) 數(shù)據(jù)結(jié)構(gòu) 動態(tài)規(guī)劃 圖 樹 序列 【正文】【引言】一個簡單的例子：給出N個數(shù)字(數(shù)字會比較大)，然后給出一些詢問，詢問一個數(shù)字有沒有在給出的N個數(shù)字當(dāng)中。事實上，這兩個方面在實際運(yùn)用中往往不是獨(dú)立的，通常需要聯(lián)合運(yùn)用。［例一］金明的預(yù)算方案及其加強(qiáng)版金明的預(yù)算方案【題意描述】給出N個物品，每個物品都有一個權(quán)值(50000)和一個價格(10000)。但是題目與背包卻有一些差別：附件不能被直接購買。狀態(tài)轉(zhuǎn)移方程：f[a][b]=Max{f[c1][b1]+f[c2][b2]+f[c3][b3]...f[ck][bk]}+score[a]?！緮?shù)據(jù)組織方案二】上面我們把本題同01背包進(jìn)行了類比。weight[i][k]表示分組后第i個對象的第k種購買方案的總權(quán)值。郁悶的金明【題意描述】給出N個物品，可以直接被購買的稱為主件，而不能直接被購買的稱為附件，附件只有當(dāng)其主件被購買了才能被購買，一個主件可以有任意多個附件，附件沒有下一級附件。自然，我們當(dāng)然嘗試用原題中的算法來套本題。如下圖：這樣做的好處是：一個附件能被購買的必要條件就是在其前面的最近的主件被購買了。分情況進(jìn)行狀態(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)時間復(fù)雜度同樣是O(NM)。N60M3200【問題分析】現(xiàn)在題目在原題的基礎(chǔ)上不僅放寬了附件的個數(shù)，還放寬了附件的層數(shù)，如圖所示：從上圖中，我們可以對本題有一個感性的認(rèn)識：關(guān)系又“寬”又“深”?，F(xiàn)在的題目是不是也可以類似解決呢？【組織數(shù)據(jù)方案四】算法3相對來說比較算法2更加一般，所以現(xiàn)在我們再回過頭來研究一下算法3，希望在分析過程中找到一些靈感。如果i是附件，那么實際上在到達(dá)下一個主件以前，i后面的附件是都不會被購買的。這一結(jié)論似乎很顯然，但是我們并不是要在樹結(jié)構(gòu)中用這一結(jié)論?，F(xiàn)在我們來設(shè)計動態(tài)規(guī)劃算法：定義：cost[i]表示第i個物品的價格weight[i]表示第i個物品的權(quán)值F[i][j]表示從第i個物品到第n個物品，最多花費(fèi)j元，能得到的最大權(quán)值和。反思這一題的幾個不同難度的版本，不難發(fā)現(xiàn)我們最終都用線形模型上的動態(tài)規(guī)劃取代了容易想到的樹形動態(tài)規(guī)劃算法。也就是說：樹的形態(tài)決定了在狀態(tài)轉(zhuǎn)移的時候要進(jìn)行額外的枚舉。要求對于每一個節(jié)點(diǎn)，求：其中(1=N=105)【問題分析】對于要求的后面兩個值，我們很容易想到O(Nlog2(N))的算法：樹上除其子孫節(jié)點(diǎn)外比該節(jié)點(diǎn)大的節(jié)點(diǎn)總數(shù)：直接排序，在待統(tǒng)計節(jié)點(diǎn)前的與該節(jié)點(diǎn)權(quán)值不同的個數(shù)再減去問題1的答案即為所求。但是這些數(shù)據(jù)結(jié)構(gòu)都是用于線型序列統(tǒng)計的，并且似乎沒有改造版本用于樹形結(jié)構(gòu)。元素相比較都指其權(quán)值大小相比較。下面我們研究轉(zhuǎn)化后的問題：【數(shù)據(jù)組織方案一】我們不對數(shù)據(jù)進(jìn)行更深入的組織，直接利用先根遍歷序，
高考資料相關(guān)推薦
鄂ICP備17016276號-1