淺談數(shù)據(jù)的合理組織(已修改)
2025-07-12 06:12 本頁(yè)面
【正文】 淺談數(shù)據(jù)的合理組織 【摘要】信息學(xué)是一門(mén)高深的學(xué)科，它正在高速的發(fā)展。隨著信息學(xué)的發(fā)展，其題目中的關(guān)系也變得越來(lái)越錯(cuò)宗復(fù)雜，給我們解題帶來(lái)困難。對(duì)數(shù)據(jù)進(jìn)行合理地組織，正是我們面對(duì)上述題目時(shí)的一種有效手段。本文用幾個(gè)經(jīng)典例題從數(shù)據(jù)的結(jié)構(gòu)和順序兩個(gè)方面進(jìn)行合理組織，達(dá)到優(yōu)化模型或是提升算法效率的目的。介紹了“合理組織數(shù)據(jù)”在信息學(xué)中建立模型和優(yōu)化算法方面的一些應(yīng)用，例題包含了動(dòng)態(tài)規(guī)劃、數(shù)據(jù)結(jié)構(gòu)、圖論類型的題目。目的在于引起讀者對(duì)于數(shù)據(jù)的合理組織的關(guān)注，并在今后的解題中能積極并靈活地運(yùn)用這一手段。【關(guān)鍵字】組織數(shù)據(jù) 數(shù)據(jù)結(jié)構(gòu) 動(dòng)態(tài)規(guī)劃 圖 樹(shù) 序列 【正文】【引言】一個(gè)簡(jiǎn)單的例子：給出N個(gè)數(shù)字(數(shù)字會(huì)比較大)，然后給出一些詢問(wèn)，詢問(wèn)一個(gè)數(shù)字有沒(méi)有在給出的N個(gè)數(shù)字當(dāng)中。當(dāng)然我們有很多已知的辦法：HASH表、TRIE、預(yù)排序+二分查找……這些算法都是通過(guò)對(duì)數(shù)據(jù)進(jìn)行合理的組織而起到了減少工作量的作用。不同的是HASH表和TRIE是利用數(shù)據(jù)形式的重新組織，而預(yù)排序＋二分查找是通過(guò)對(duì)數(shù)據(jù)順序的重新組織來(lái)達(dá)到優(yōu)化算法的目的的。我們組織數(shù)據(jù)，主要就是通過(guò)從“形式”和“順序”這兩個(gè)角度來(lái)考慮。事實(shí)上，這兩個(gè)方面在實(shí)際運(yùn)用中往往不是獨(dú)立的，通常需要聯(lián)合運(yùn)用。我們已經(jīng)學(xué)習(xí)了很多經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，它們都是合理組織數(shù)據(jù)的表現(xiàn)。在優(yōu)化算法中有很好表現(xiàn)。對(duì)數(shù)據(jù)組織的合理化，不僅在我們?cè)O(shè)計(jì)算法時(shí)能起到優(yōu)化程序效率的作用，有時(shí)，我們?cè)诮⒔忸}模型時(shí)，合理地組織數(shù)據(jù)可能給我們提供新的思考角度，從而優(yōu)化解題模型，例一就是這樣的一個(gè)例子。［例一］金明的預(yù)算方案及其加強(qiáng)版金明的預(yù)算方案【題意描述】給出N個(gè)物品，每個(gè)物品都有一個(gè)權(quán)值(50000)和一個(gè)價(jià)格(10000)。我們稱可以直接被購(gòu)買(mǎi)的物品為主件，稱不能被直接購(gòu)買(mǎi)的物品為附件，附件只有當(dāng)其主件被購(gòu)買(mǎi)了才能被購(gòu)買(mǎi)，一個(gè)主件最多有兩個(gè)附件，附件沒(méi)有下一級(jí)附件。任務(wù) 購(gòu)買(mǎi)一些物品，總價(jià)格不超過(guò)M，使得被購(gòu)買(mǎi)的物品的權(quán)值之和最大。N3200 M60【簡(jiǎn)要分析】我們很容易聯(lián)想到經(jīng)典的動(dòng)態(tài)規(guī)劃之01背包問(wèn)題。但是題目與背包卻有一些差別：附件不能被直接購(gòu)買(mǎi)?！緦?duì)數(shù)據(jù)的初步組織】主件與附件之間是樹(shù)形的關(guān)系。組織一下數(shù)據(jù)，如下圖：（圖1）如圖所示：主件1沒(méi)有附件，主件2有兩個(gè)附件，主件3只有一個(gè)附件?！緮?shù)據(jù)組織方案一】假設(shè)我們忽略數(shù)據(jù)的特殊性，單從樹(shù)結(jié)構(gòu)考慮，我們?nèi)菀紫氲降囊粋€(gè)算法是：給所有主件加上一個(gè)“級(jí)超主件”，把原來(lái)的所有主件都變成“超級(jí)主件”的附件，如下圖： (圖2)【算法一】這樣，在這棵樹(shù)上，我們可以設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法： 定義：cost[a]表示a節(jié)點(diǎn)所代表的物品的價(jià)格score[a]表示a節(jié)點(diǎn)所代表的物品的得分狀態(tài)f[a][b]表示以節(jié)點(diǎn)a為根的子樹(shù)，總共花費(fèi)不超過(guò)b元的最多得分。狀態(tài)轉(zhuǎn)移方程：f[a][b]=Max{f[c1][b1]+f[c2][b2]+f[c3][b3]...f[ck][bk]}+score[a]。其中ci為a的子節(jié)點(diǎn)；∑bi=bcost[a]。這樣枚舉的效率顯然不高！我們可以用左兒子右兄弟表示法來(lái)表示這一棵樹(shù)，將原樹(shù)轉(zhuǎn)化成二叉樹(shù)，則我們?cè)谶M(jìn)行狀態(tài)轉(zhuǎn)移的時(shí)候只用考慮給左兒子分配多少錢(qián)。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]}這樣我們可以得到一個(gè)理論 參見(jiàn)《算法藝術(shù)與信息學(xué)競(jìng)賽》貪食的九頭龍中對(duì)算法復(fù)雜度的分析復(fù)雜度為O(NM2)的算法，但是對(duì)于本題的數(shù)據(jù)范圍來(lái)說(shuō)，這個(gè)復(fù)雜度并不太理想?！緮?shù)據(jù)組織方案二】上面我們把本題同01背包進(jìn)行了類比。發(fā)現(xiàn)兩道題之間的差別：附件不能被直接購(gòu)買(mǎi)。顯然，如果題目中沒(méi)有附件，那么本題即為標(biāo)準(zhǔn)的01背包問(wèn)題。我們回到題目并考慮其特殊性：。這樣，顯然對(duì)于（圖一）中每一組（主件＋附件），可以作為整體考慮。對(duì)于每一組，可能的購(gòu)買(mǎi)方案最多只有：這樣，我們可以借鑒經(jīng)典的01背包動(dòng)態(tài)規(guī)劃，把每一組看作一個(gè)對(duì)象，取值和花費(fèi)對(duì)應(yīng)最多五種。【算法二】cost[i][k]表示分組后第i個(gè)對(duì)象的第k種購(gòu)買(mǎi)方案的花費(fèi)。weight[i][k]表示分組后第i個(gè)對(duì)象的第k種購(gòu)買(mǎi)方案的總權(quán)值。F[i][j]表示前i個(gè)對(duì)象最多花費(fèi)j元，能得到的最大權(quán)值。F[i][j]=max(F[i1][jcost[i][k]]+weight[i][k])。其中1=k=5且cost[i][k]=j 狀態(tài)總數(shù)：O(NM)轉(zhuǎn)移代價(jià)：O(1)這樣，我們得到了一個(gè)時(shí)間復(fù)雜度為O(NM)的優(yōu)秀算法。郁悶的金明【題意描述】給出N個(gè)物品，可以直接被購(gòu)買(mǎi)的稱為主件，而不能直接被購(gòu)買(mǎi)的稱為附件，附件只有當(dāng)其主件被購(gòu)買(mǎi)了才能被購(gòu)買(mǎi)，一個(gè)主件可以有任意多個(gè)附件，附件沒(méi)有下一級(jí)附件。每個(gè)物品都有一個(gè)權(quán)值(50000)。任務(wù) 購(gòu)買(mǎi)一些物品，總價(jià)格不超過(guò)M，使得被購(gòu)買(mǎi)的物品的權(quán)值之和最大。N60M3200【問(wèn)題分析】題目放寬了“一個(gè)主件最多可以有兩個(gè)附件”這個(gè)限制，其它條件不變。自然，我們當(dāng)然嘗試用原題中的算法來(lái)套本題。實(shí)際上，這時(shí)候原來(lái)的算法1依然適用，復(fù)雜度仍為O(NM2)。但是對(duì)于利用原
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1