對背包問題的一些研究

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

2、是對于容量很大的數(shù)據(jù)就會花費(fèi)太多的時間，而且如果重量是實(shí)數(shù)而不是整數(shù)就根本無法進(jìn)行。對于這個問題，我曾看到一本書上提供了用函數(shù)間斷點(diǎn)的方法來解決?；舅悸肥菍τ诋?dāng)前的情況，用一系列二元組來描述。二元組是（wv）的形式，表示重量為w時最大價(jià)值為v。每加入一個新的物體時，對當(dāng)前的所有二元組進(jìn)行拓展，并和原來的合并得到新的二元組集。如：容量為10，有5個物體，重量為35197，價(jià)值為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)所以最大價(jià)值為55，這與我們用動態(tài)規(guī)劃的出的結(jié)論是一樣的。動態(tài)規(guī)劃表格如下：001111111111111111001111282828393939666172834343945456661728343439495566617283435394955而我們得到二元組集正是這個函數(shù)的間斷點(diǎn)分布。當(dāng)時看這個算法時，書上介紹其時間復(fù)雜度為O(2n)。因?yàn)槊看渭尤胍?/p>

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