對(duì)背包問(wèn)題的一些研究

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

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

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

4、(16)(417)(528)(634)(735)(839)(949)(1055)所以最大價(jià)值為55，這與我們用動(dòng)態(tài)規(guī)劃的出的結(jié)論是一樣的。動(dòng)態(tài)規(guī)劃表格如下：001111111111111111001111282828393939666172834343945456661728343439495566617283435394955而我們得到二元組集正是這個(gè)函數(shù)的間斷點(diǎn)分布。當(dāng)時(shí)看這個(gè)算法時(shí)，書(shū)上介紹其時(shí)間復(fù)雜度為O(2n)。因?yàn)槊看渭尤胍?/p>

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