基于背包問題與貪心算法的高效數據整合系統

◆劉順程 岳思穎 李楠鍵

基于背包問題與貪心算法的高效數據整合系統

◆劉順程 岳思穎 李楠鍵

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

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

背包問題；貪心算法；數據整合；容器組件

0 引言

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

1 算法背景于傳統方法

1.1貪心算法

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

1.2背包問題

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

1.3傳統方案與潛在問題

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

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

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

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

2.1系統架構

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

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

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

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

2.2系統執行流程

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

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

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

（4）從數據庫讀取數據整合所需的所有相關數據；

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

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

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

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

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

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

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

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

（13）所有調用完成，系統結束。

3 結束語

進入互聯網+時代，眾多行業都需要更高效精準的數據管理方案。基于背包問題與貪心算法的高效數據整合系統，能將數據集進行自動整合并提供更安全、更高效的解決方案，同時有效解決了傳統方案中存在的安全隱患。相信該系統在未來的大數據領域中會得到更好的發展。

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

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