背包問題的進(jìn)一步討論

1、1背包問題的進(jìn)一步討論摘要摘要：本文提出了背包問題的一種基于屬性論的啟發(fā)式算法。文章在開篇綜述背包問題的一些基本情況后，接著介紹了屬性論的一些基本觀點、方法和理論，包括定性映射模型，人工神經(jīng)元模型與定性映射模型的關(guān)系，量質(zhì)轉(zhuǎn)換程度函數(shù)等等。隨后結(jié)合貪婪算法和背包核問題的思想，我們給出了物件基于核的一個定性映射。在根據(jù)背包的核問題的具體情況對屬性論中傳統(tǒng)的Gauss型轉(zhuǎn)換程度作了必要的改進(jìn)之后，我們給出了背包問題基于屬性論的一個近似轉(zhuǎn)化優(yōu)

2、化算法并且根據(jù)此算法用Java語言設(shè)計了背包問題軟件包。軟件包的設(shè)計充分結(jié)合了Java語言的特點，具有高性能和高的可擴(kuò)展性，提供了可擴(kuò)展的接口以方便其他應(yīng)用程序擴(kuò)展和調(diào)用。關(guān)鍵字關(guān)鍵字:背包問題，核問題，屬性論方法，定性映射，轉(zhuǎn)化程度函數(shù)31引言引言背包問題是一個在運籌學(xué)領(lǐng)域里常見的典型NPC難題。工廠里的下料問題，管理中的資源分配，資金預(yù)算，投資決策，裝載問題等均可建模為背包問題。對該問題的求解方法的研究無論是在理論上，還是在實踐中都

3、具有重要意義。對于背包問題，己有的求解方法可分為精確算法(如動態(tài)規(guī)劃，分支定界等)和近似算法(如貪婪法，蟻群算法，遺傳算法等)兩大類。因為精確算法的時間復(fù)雜性都是呈指數(shù)增長的，所以從六十年代逐漸提出了一些近似算法。1.11.1歷史背景歷史背景背包問題(Knapsackproblem)在50年代末期被Dantzig首次提出之后，在近年來被廣泛的研究。這不僅是因為背包問題在工業(yè)和金融投資領(lǐng)域能得到直接的應(yīng)用，更是因為很多理論上的原因。很多整

4、數(shù)規(guī)劃的問題的解決都依賴于一個高效的背包問題解法(在這些整數(shù)規(guī)劃問題中，每當(dāng)需要定界的時候我們都需要解決一個背包子問題，因此，一個高效的背包問題解法就顯得非常有必要。所有的背包問題都可以定性的描述為，從給定的物品集合中選擇出一個子集，在不超出所有背包的負(fù)載的前提下，實現(xiàn)利益最大化。背包問題的不同種類的判定，是根據(jù)物品和背包的類型:在01背包問題(Knapsackproblem)中，每一個物品最多被選擇一次，而與之相對應(yīng)的有界背包問題。(

5、BundedKnapsackproblem)中能選擇的物品數(shù)則可以在某個范圍內(nèi)取值再比如多選擇背包問題(MulticonstrainedKnapsackproblem)是說某幾個物體必須選擇一個或多個，而多背包的背包問題(MultiKnapsackproblem)則是說某些背包必須同時被裝滿。在這些背包問題家族中，最通用的形式是多條件約束背包問題伍加(MulticonstrainedKnapsackproblem)，而這在實質(zhì)上就是正系

6、數(shù)的整數(shù)規(guī)劃問題(IntegerProgramming)。在下面我們將給出各種背包問題的數(shù)學(xué)模型。背包問題屬于組合最優(yōu)化問題。一般的，最優(yōu)化問題(OptimizationProblem)由目標(biāo)函數(shù)(ObjectiveFunction)和約束條件(Constraints)兩部分構(gòu)成:Minimzief(x)=f(x，，xZ，…，xn)Subjectotx=(xl，xZ，…，xn)∈Scx將滿足所有約束條件的解空間s稱為可行域(Feasib

7、leRegion)，可行域中的解稱為可行解(FeasibleSolution)將可行域中使目標(biāo)函數(shù)最小的解稱為最優(yōu)解(OptimalSolution)。對于最大化問題，可將目標(biāo)函數(shù)乘以(1)轉(zhuǎn)化為最小化問題求解。當(dāng)x或S為離散集合構(gòu)成的解空間時，這類最優(yōu)化問題稱為組合最優(yōu)化問題(CombinataialOptimizationproblem)?；趯傩哉摰?1背包問題算法研究衡量一個算法的好壞通常用算法中的加、減、乘、除和比較等基本運算