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