◆劉順程 岳思穎 李楠鍵

基于背包問題與貪心算法的高效數(shù)據(jù)整合系統(tǒng)

◆劉順程 岳思穎 李楠鍵

（重慶郵電大學軟件工程學院 重慶 400065）

隨著互聯(lián)網(wǎng)+時代的到來，各行各業(yè)為使其業(yè)務更易于管理，紛紛將數(shù)據(jù)以及結構化報表通過計算機進行動態(tài)生成；這使得如何高效處理數(shù)據(jù)并生成結構化體系成為了當務之急，比如生成線上考試試卷、商品的規(guī)格參數(shù)列表、公司流程報表等。本文以高效數(shù)據(jù)整合算法為研究重點，分別介紹了傳統(tǒng)數(shù)據(jù)整合的方法與缺陷，同時重點介紹了基于背包問題與貪心算法的高效數(shù)據(jù)整合算法——一種更高效安全的數(shù)據(jù)整合框架。

背包問題；貪心算法；數(shù)據(jù)整合；容器組件

0 引言

隨著互聯(lián)網(wǎng)的普及，黨和國家號召充分利用互聯(lián)網(wǎng)資源，使得將各行各業(yè)的紙質化資料進行網(wǎng)絡化、虛擬化成為了趨勢。當前傳統(tǒng)的數(shù)據(jù)整合方法在高并發(fā)環(huán)境中由于效率較低，易導致服務器系統(tǒng)崩潰。于是，基于背包問題與貪心算法的高效數(shù)據(jù)整合系統(tǒng)應運而生。

1 算法背景于傳統(tǒng)方法

1.1貪心算法

貪心算法的基本思路是從問題的某一個初始解出發(fā)一步一步地進行,根據(jù)某個優(yōu)化測度,每一步都要確保能獲得局部最優(yōu)解。每一次只考量一個數(shù)據(jù)，是否選取該數(shù)據(jù)取決于是否滿足局部最優(yōu)的條件，直到把所有的數(shù)據(jù)枚舉完成，或者滿足了某優(yōu)化條件后，算法終止。從全局看來，每種選擇方案依賴于已作出的選擇，而不依賴于未作出的選擇；因此最終的結果也成為了該問題的最優(yōu)方案[1]。

1.2背包問題

背包問題是一種組合優(yōu)化的NP完全問題。問題可以簡單描述為：給定一組物品和一個背包，每個物品有其對應的重量和價值，而背包則有其所能裝載重量的上限。因此，我們要通過合理選擇來使得在不超過背包裝載量的上限下，背包所裝載物品的價值盡可能地大。背包問題可以抽象成一個容器-物品填充模型，即當前可供選擇的物品中，能否通過合理選擇，使得容器被填滿且其承載價值達到最大[2]。

1.3傳統(tǒng)方案與潛在問題

在傳統(tǒng)數(shù)據(jù)整合方案中，常常使用某種單一的數(shù)據(jù)類為物品，需求結構體為容器，來進行自動化數(shù)據(jù)組合生成需求結構。首先構建結構體容器，使用相應約束條件定義背包容量，隨后以每條數(shù)據(jù)的特性來進行容器填充，當容器中的約束條件達到預設值后，數(shù)據(jù)組合成功；若在遍歷完所有數(shù)據(jù)后仍沒有達到背包容器預設值，則數(shù)據(jù)組合失敗。然后又將另一種數(shù)據(jù)類定義為物品，相應需求結構體為容器，繼續(xù)進行上述操作，直到將所有的結構體所需的數(shù)據(jù)填充完成，數(shù)據(jù)整合結束。

隨著大數(shù)據(jù)時代的來臨，這種傳統(tǒng)方案暴露出了組合效率低下、存在線程死鎖風險等諸多問題。例如，在實驗環(huán)境中，數(shù)據(jù)類物品存放于內存中，遍歷數(shù)據(jù)能迅速完成；但是在實際生產環(huán)境中，數(shù)據(jù)類物品存放于數(shù)據(jù)庫中。相比于內存讀取，數(shù)據(jù)庫的讀取速度是及其緩慢的；面對實際環(huán)境中的多線程、高并發(fā)的服務操作，傳統(tǒng)數(shù)據(jù)組合算法會對數(shù)據(jù)庫進行反復讀寫，這樣極易造成數(shù)據(jù)庫連接數(shù)達到上限，從而引起數(shù)據(jù)庫阻塞，程序線程死鎖等惡劣情況，導致整個系統(tǒng)崩潰。

2 基于背包問題與貪心算法的高效數(shù)據(jù)填充方案

本方案的基于背包問題與貪心算法的高效數(shù)據(jù)填充系統(tǒng)，包括多背包容器組件、物品屬性組件、本地模擬填充組件和數(shù)據(jù)存儲組件。

2.1系統(tǒng)架構

多背包容器組件，用于將傳統(tǒng)背包方案的單個容器擴充為多個容器用于數(shù)據(jù)填充中對多種數(shù)據(jù)結構體的描述。比如在實際的數(shù)據(jù)整合過程中，我們所需的填充項一定不止一個。于是，我們使用多背包容器組件來描述整個數(shù)據(jù)填充項集合，使得單次運行該算法即可完成所有的數(shù)據(jù)填充，避免了多次操作數(shù)據(jù)庫易引起的問題。

物品屬性組件，用于將傳統(tǒng)方案中的數(shù)據(jù)集轉化為虛擬物品，虛擬物品在初始化后，需要調用本地模擬填充模塊進行屬性賦值。比如將容器所需的某種數(shù)據(jù)虛擬化為物品，而該物品屬性數(shù)量一定大于傳統(tǒng)背包物品的兩個屬性（V，W），所以我們需要調用本地模擬填充模塊進行數(shù)據(jù)庫查詢，將數(shù)據(jù)物品項的屬性進行賦值，使其得到多重屬性，以便完善后續(xù)的填充需求。

本地模擬填充組件，用于將傳統(tǒng)數(shù)據(jù)整合算法中，反復讀取數(shù)據(jù)庫來提取數(shù)據(jù)進行容器填充的過程轉化為只進行一次數(shù)據(jù)庫提取；獲取所有數(shù)據(jù)信息后，首先對物品屬性組件的每個物品進行屬性填充，從而記錄整合時候每個結構體應具備的約束條件；隨后使用貪心算法，在本地容器組件中對容器進行數(shù)據(jù)填充，填充規(guī)則按照容器定義以及物品屬性，并使用貪心算法根據(jù)屬性權值進行優(yōu)先集填充；直到所有的容器填充完成，本地模擬填充結束。

數(shù)據(jù)存儲組件，用于將傳統(tǒng)整合算法中通過模塊約束條件在數(shù)據(jù)庫中選取數(shù)據(jù)并進行數(shù)據(jù)庫存儲轉化為通過本地模擬填充容器保存的相關數(shù)據(jù)直接存儲在數(shù)據(jù)庫中；從而讓系統(tǒng)獲得數(shù)據(jù)整合結果，使得數(shù)據(jù)庫的讀取次數(shù)再次減少，提升程序運行效率。

2.2系統(tǒng)執(zhí)行流程

（1）通過需求結構體構造多個背包，并且設置為虛擬容器；

（2）向容器添加描述其屬性（如某某數(shù)據(jù)容器），直到所有虛擬容器添加完成；

（3）根據(jù)需求，創(chuàng)建單個或多個物品組件（使用容器完成），初始化物品組件的屬性均為Null；

（4）從數(shù)據(jù)庫讀取數(shù)據(jù)整合所需的所有相關數(shù)據(jù)；

（5）根據(jù)數(shù)據(jù)與相關需求，將S3中創(chuàng)建的物品組件進行屬性填充，為每個物品容器的屬性進行賦值，直到所有物品組件填充完畢；

（6）根據(jù)背包問題，依照貪心算法，對S1中創(chuàng)建的背包容器進行物品填充，以當前容器指向的描述物品（屬性），對物品的當前的屬性權值由高到低為策略繼續(xù)選擇，將選擇結果保存在當前背包容器中；

（7）判斷本地模擬填充的背包容器是否滿足需求數(shù)據(jù)的約束。若滿足則準備開始填充下一個背包容器執(zhí)行S8，否則執(zhí)行S9；

（8）判斷背包中所有容器是否填充完成，若完成則執(zhí)行S12,否則執(zhí)行S6；

（9）判斷在剩余的物品數(shù)據(jù)（當前物品沒有匹配的屬性）中是否有物品集合可供選擇，若有執(zhí)行S10，否則執(zhí)行S11；

（10）調整該物品的屬性權值，允許背包容器進行填充，執(zhí)行S6；

（11）拋出錯誤，算法運行失敗，返回空值，系統(tǒng)結束；

（12）將本地模擬填充模塊填充完成的背包容器數(shù)據(jù)，存儲在數(shù)據(jù)庫中；

（13）所有調用完成，系統(tǒng)結束。

3 結束語

進入互聯(lián)網(wǎng)+時代，眾多行業(yè)都需要更高效精準的數(shù)據(jù)管理方案?；诒嘲鼏栴}與貪心算法的高效數(shù)據(jù)整合系統(tǒng)，能將數(shù)據(jù)集進行自動整合并提供更安全、更高效的解決方案，同時有效解決了傳統(tǒng)方案中存在的安全隱患。相信該系統(tǒng)在未來的大數(shù)據(jù)領域中會得到更好的發(fā)展。

[1]常友渠，肖貴元，曾敏.貪心算法的探討與研究[J].重慶電力高等?？茖W校學報，2008.

[2]史今馳.背包問題的實用求解算法研究[D].山東;山東大學，2005.