1、子集和問(wèn)題的完全多項(xiàng)式近似方案算法子集和問(wèn)題的完全多項(xiàng)式近似方案2 0 1 2年2月一、 作業(yè)背景：1 、 子集和問(wèn)題簡(jiǎn)介子集和問(wèn)題的一個(gè)實(shí)例是一個(gè)對(duì) (S,t), 其中 S 是一個(gè)正整數(shù)的集合 x 1, x 2, x3,., x n ,t為一個(gè)正整數(shù)。這個(gè)判定問(wèn)題是判定是否存在 S 的一個(gè)子集，使得其中的數(shù)加起來(lái)恰為目標(biāo)值 t 。這個(gè)問(wèn)題是 NP 完全的。與此判定問(wèn)題相聯(lián)系的最優(yōu)化問(wèn)題常常出現(xiàn)于實(shí)際應(yīng)用中。在這種最優(yōu)化問(wèn)題中，希 望找到x1,x2xn 的一個(gè)子集，是其中元素相加之和盡可能地大，但不能大于t。例如, 假設(shè)我們有一輛能裝不多于 t 磅重的貨的卡車(chē)，并有 n 個(gè)不同的盒子要裝運(yùn)，其

2、中 第 i 個(gè)的重量為 xi 磅。要在不超過(guò)重量極限的前提下，將貨盡可能的裝滿(mǎn)卡車(chē)。2 、 開(kāi)發(fā)平臺(tái)Eclipse + Jdk 1.7二、 問(wèn)題分析：子集和問(wèn)題實(shí)際上是背包問(wèn)題的特例 , 就是背包問(wèn)題中項(xiàng)的值和他們的大小相同。課 本上給的算法實(shí)質(zhì)就是個(gè)動(dòng)態(tài)規(guī)劃的方法。按照它給的偽代碼實(shí)現(xiàn)之后，可以得出一個(gè)精 確解。后來(lái)參考了算法導(dǎo)論書(shū)中對(duì)子集和采取的完全多項(xiàng)式時(shí)間近似方案來(lái)進(jìn)行處理。(一) ，給出一個(gè)指數(shù)時(shí)間的準(zhǔn)確算法假設(shè)對(duì) S 的每個(gè)子集 S '，都計(jì)算出 S '中所有元素的和。接著，在所有元素和不 超過(guò) t 的子集中選擇 其和最接近 t 的那個(gè)子集。顯然，這一算法將返回最優(yōu)

3、解。但它可 能需要指數(shù)級(jí)的時(shí)間。為了實(shí)現(xiàn)這個(gè)算法，可以采用一個(gè)迭代過(guò)程：第i 輪迭代中，計(jì)算L +x 的所有子集的元素和，計(jì)算的根底是 x 1, x 2, x 3,., x i -1的所有子集和。在此計(jì)算過(guò)程中，一旦某個(gè)特定的子集 S '的和超過(guò)了 t, 就沒(méi)有必要再對(duì)它進(jìn)行處理了， 因?yàn)?S '的超集都不會(huì)成為最優(yōu)解。下面給出這一策略的一個(gè)實(shí)現(xiàn)。EXACT-SUBSET-SUM 的輸入為一個(gè)集合 S=x 1, x 2, x 3,., x n 和一個(gè)目標(biāo)值t ；這個(gè)過(guò)程以迭代的方式計(jì)算列表 L i , 其中列出了 x 1, x 2, x 3,., x i 的所有子集的和，這些和

4、值都不超過(guò)目標(biāo)值 t 。接著，它返回 L n 中的最大值。如果 L 是一個(gè)由正整數(shù)所構(gòu)成的表， x 是一個(gè)正整數(shù)，我們用 L +x 來(lái)表示通過(guò)對(duì) 2 中每個(gè)元素增 i2 , 3, 5, 9，貝V L+2= 3, 4, 5, 7, 11力口 x而導(dǎo)出的整數(shù)列表。例如,如果L =1 ，。我們也對(duì)集合應(yīng)用這個(gè)記號(hào)，因而 S +x =s +x :x S 我們還用到一個(gè)輔助過(guò)程 MERGE-LISTS L , L ',返回對(duì)它的兩個(gè)已排序的輸入 列表 L 和 L '合并及刪除重復(fù)值后所產(chǎn)生的排序列表。EXACT-SUBSET-SUM S,t 1 n |S|2 L0 J3 for I J

5、1 to ndo L i JMERG-ELISTL i -1, L i +x remove from L i every element that is greater than treturn the largest element in L n即P =P i -1 P i +x i ,可以通過(guò)對(duì)i的歸納來(lái)證明，表 L i是一個(gè)包含P i中所有值不大于 t 的元素有序表。因?yàn)?L i 的長(zhǎng)度可大至 2,一般來(lái)說(shuō) EXACT-SUBSET-SUM 是一個(gè)指數(shù)時(shí)間的算法。二,完全多項(xiàng)式時(shí)間近似方案對(duì)子集和問(wèn)題我們可以導(dǎo)出一個(gè)完全多項(xiàng)式近似方案,在每個(gè)列表上L i 被創(chuàng)立后,對(duì)它進(jìn)行修整,具體思想

6、是如果其中有兩個(gè)值比擬接近,那么處于尋找近似解的目的, 沒(méi)有必要同時(shí)保存這兩個(gè)數(shù)。更準(zhǔn)確的說(shuō)，我們采用一個(gè)修正參數(shù)3 ,滿(mǎn)足0y < z < y 1+ 3 可以將這樣一個(gè) z 看成是新表 L ' 中代表 y 的。每個(gè) y 都有一個(gè)滿(mǎn)足不等式的 z 的 替換。如：L =10,11,12,15,20,21,22,23,24,29貝可以休整 L 而得L ' =10,12,15,20,23,29其中被刪除的值 11由 10來(lái)代表，被刪除的值 21和22由 20代表，被刪除的值 24由 23 代表。表的休整版本中的元素也是原表的元素，對(duì)一個(gè)表加以休整后，可以大大減少表 中的元

7、素，同時(shí)還可以在表中為每個(gè)人被從該表中刪除的元素保存一個(gè)與其很接近的且略 小一些的代表值。在給定L和S的情況下，在時(shí)間 0(m)內(nèi)休整一個(gè)輸入表L =,假定 L 已經(jīng)排成單調(diào)遞增序。該過(guò)程的輸入是一個(gè)休整過(guò)的有序表TRIM (L ,$)1m- |L |2 L '3 last - y 14 for i - 2 to m5 do if y i >last.(1+S )6 Then append y i onto the end of L7 last -y iReturn L 'L '中，僅當(dāng)它L 的元素被按照單調(diào)遞增次序加以?huà)呙瑁粋€(gè)數(shù)被參加返回的列表 是 L 的第

8、一個(gè)元素，或者如果它不能由最近被放入 L '的數(shù)來(lái)代表。給定過(guò)程 TRIM 后，可以如下構(gòu)造近似方案。這個(gè)過(guò)程的輸入為包含 n 個(gè)整數(shù)的集合S=x 1, x 2, x 3,., x n (以任意次序放置)，一個(gè)目標(biāo)整數(shù) t,. 以及一個(gè)“近似參數(shù) £，此處：它返回一個(gè)值 Z，該值落在最優(yōu)解的1+ £倍內(nèi)。APPROX-SUBSET-SUM (S, t, )1. n -|S|2. L 0 -3. for i - to n4. do L i -MERG-ELISTS(L i -1， L i -1+x i )5. L i TRIM(L i , /2n )6. Remove

9、 from L i every element that is greater than t7. let z be the largest value in L n8. return z第 2 行將表 L 0 初始化為僅包含元素 0 的一個(gè)表。第 3 6 行間 for 循環(huán)的效果是 : 將 L i 作為一個(gè)包含集合 P i 的適當(dāng)休整版本去掉大于 t 的元素來(lái)計(jì)算 . 因?yàn)?L i 是從 L i -1 構(gòu)造出來(lái)的，故必須保證重復(fù)的休整不會(huì)引入太多的不準(zhǔn)確性。例子如下 :S=104,102,201,101且 t=308 , & =0.40.修整參數(shù) 3 為 & /8=0.05。、

10、APPROX-SUBSET-SU在所指示的各 行上計(jì)算出如下值：第2行：L 0=第 4 行: L 1=第 5 行： L 1=第 6 行： L 1=第 4 行： L 2=第 5 行： L 2= 第 6 行： L 2= 第 4 行： L 3= 第 5 行： L 3= 第 6 行： L 3= 第 4 行： L 4= 第 5 行： L 4= 第 6 行： L 4= 該返回值而 302 是在 =40%內(nèi)的。實(shí)際上，是在其2% 之內(nèi)。關(guān)于APPROX-SUBSET-SI是關(guān)于子集和問(wèn)題的一個(gè)完全多項(xiàng)式時(shí)間近似方案的證明， 參見(jiàn)?算法導(dǎo)論? 第 864頁(yè)定理 35.8 。(三) ，相關(guān)研究為了做比擬分析，在

11、能求出準(zhǔn)確解答的情況下，我們還用回溯法寫(xiě)了求精確解的方法。 雖然能得出全部解答，但是如果子集項(xiàng)數(shù)稍微多一點(diǎn)根本上就得不出答案了。代碼如下：public class SumOfSub private int w ; /用來(lái)存放子集 private int m ; / 用來(lái)存放子集和 tprivate int x ; /用來(lái)判斷該子集是否能用來(lái)構(gòu)成目標(biāo)子集和public SumOfSub(int w, int m, int n) this . w = w; this . m = m; this .x = new int n; public void computeSumOfSub(int s, i

12、nt k, int r) x k = 1;if (s+w k = m ) printResult(k); else if (s+w k+w k+1/ 仍有別的可能可以繼續(xù)求出別的方案 , 不要當(dāng)前的 wk 還有沒(méi)有別的可能 , 前提是 已經(jīng)排好序了if (s+r-w k>=m && s+w k+1效果如圖：x k = 0; computeSumOfSub(s, k+1, r-w k); public voidprintResult(int k) for (int i=0; i用動(dòng)態(tài)規(guī)劃的方案來(lái)解決這個(gè)問(wèn)題代碼如下：Public class DPint v=0,0;/用來(lái)放

13、 vij 從 x0 到 xi 中選出能組成 j 的最優(yōu)組合，這里是盡可能接近 jint left = t;/將目標(biāo)子集和大小付給剩下來(lái)要到達(dá)的大小 for (int i = 1; ileft) System. out .print("*"); vij = vi - 1j; else /如果當(dāng)前的項(xiàng)與從前 i-1 項(xiàng)選出到達(dá) j-1 的最優(yōu)組合的和比 vi-1j 的大 if (si + vi -1j - 1 > vi - 1j) vij = vi - 1j - 1+si; left -= si; else vij = vi - 1j; System. out .prin

14、tln(" 動(dòng)態(tài)規(guī)劃 " ); int j=t; int inOrout=; for (int i=0;i由于在java中數(shù)組下表一直報(bào)錯(cuò)，在C+中修改代碼之后得出效果如下：三、算法設(shè)計(jì)與實(shí)現(xiàn)：核心代碼如下：VeCtor andSort(VeCtor s,int x,double e,int t)/ 添加新元素到表中 int n=s.size(); for (int i=0;i vs=new VeCtor(); for(int index=0;index(1+e)*(vs.get(vs.size()-1) && s.get(index)=0 && s.get(j)>temp) s.remove(j+1); s.add(j+1, temp); /s.add(j+1, s.get(j); s.remove(j+1); s.add(j+1,s.get(j); j-; s.add(s.get(i)+x);把參加數(shù)據(jù)的過(guò)程和排序過(guò)程以及去掉相似項(xiàng)的過(guò)程都展示出來(lái)了。、四、心得總結(jié)1. 遞歸方法不