對背包問題的一些研究

1、對背包問題的一些研究江蘇靖江高級中學李哲我們對背包問題都很熟悉，這次我們要討論的是背包問題中的01背包，即在一個容量為c的背包中，放入n個物體，這n個物體重量為w[1..n]，價值為v[1..n]，要求在不超過容量限制的情況下最大的價值是多少。對于重量為整數(shù)的背包問題我們可以很快寫出動態(tài)規(guī)劃方程：f[ij]=maxf[i1j]f[i1jw[i]]v[i]其中f[ij]表示前i個物體用j個空間時能獲得的最大價值。但是這有一個很大的缺點，就

2、是對于容量很大的數(shù)據(jù)就會花費太多的時間，而且如果重量是實數(shù)而不是整數(shù)就根本無法進行。對于這個問題，我曾看到一本書上提供了用函數(shù)間斷點的方法來解決。基本思路是對于當前的情況，用一系列二元組來描述。二元組是（wv）的形式，表示重量為w時最大價值為v。每加入一個新的物體時，對當前的所有二元組進行拓展，并和原來的合并得到新的二元組集。如：容量為10，有5個物體，重量為35197，價值為112864935。則二元組集p的變化為0個物體時p=(00

3、)加入第1個物體時q=(311)p=(00)(311)加入第2個物體時q=(528)(839)p=(00)(311)(528)(839)加入第3個物體時q=(16)(417)(634)(945)p=(00)(16)(417)(528)(634)(839)(945)加入第4個物體時q=(949)(1055)p=(00)(16)(417)(528)(634)(839)(949)(1055)加入第5個物體時q=(735)(843)p=(00)

4、(16)(417)(528)(634)(735)(839)(949)(1055)所以最大價值為55，這與我們用動態(tài)規(guī)劃的出的結(jié)論是一樣的。動態(tài)規(guī)劃表格如下：001111111111111111001111282828393939666172834343945456661728343439495566617283435394955而我們得到二元組集正是這個函數(shù)的間斷點分布。當時看這個算法時，書上介紹其時間復雜度為O(2n)。因為每次加入一

5、個物體會使當前的二元集擴大到2倍左右。但是事實上沒有那么恐怖，因為有以下兩個限制條件幫我們大量剪枝：1當重量超過限制時去掉2當出現(xiàn)(aibi)和(ajbj)，并有aibj時去掉后者由此可見，要想提高算法的效率，主要要利用這兩個限制條件，因此我們可以在計算前先排一個序。那么根據(jù)什么作為排序的key呢？首先要明確的是，我們要盡量在靠近樹根的地方把枝剪掉，這樣才能剪去一片“茂密”的樹葉。從第一個限制條件看，要盡量把重的物體放在前面，才能有效地