C#用遞歸算法解決經(jīng)典背包問題

更新時間：2016年06月15日 10:55:08 作者：張玉彬

背包問題有好多版本，本文只研究0/1版本，即對一個物體要么選用，要么就拋棄，不能將一個物體再繼續(xù)細(xì)分的情況。

1.引子

　　我們?nèi)祟愂且环N貪婪的動物，如果給您一個容量一定的背包和一些大小不一的物品，裝到背包里面的物品就歸您，遇到這種好事大家一定不會錯過，用力塞不一定是最好的辦法，用腦子才行，下面就教您如何解決這樣的問題，以獲得更多的獎品。

2.應(yīng)用場景

　　在一個物品向量中找到一個子集滿足條件如下：

　　1）這個子集加起來的體積大小不能大于指定閥值

　　2）這個物品子集加起來價值大小是向量V中所有滿足條件1的子集中最大的

3.分析

　　背包問題有好多版本，本文只研究0/1版本，即對一個物體要么選用，要么就拋棄，不能將一個物體再繼續(xù)細(xì)分的情況。這種問題最簡單的方法就是找出這個向量的所有子集，如同找出冪集中的子集一樣，但這種遍歷的方法恐怕并不會被聰明的我們所使用，現(xiàn)在舉辦這些活動的電視臺也非常聰明，他們不但要求您能將物品裝進(jìn)去，而且指定操作時間，這樣當(dāng)您慢慢騰騰的裝進(jìn)去倒出來的時候，時間恐怕早就到了，最終您可能一無所獲，這可不是我們希望的結(jié)果，我們需要使用一些策略：第一次我們可以從大小小于背包容量的物品中隨意挑取一個，這樣可以盡量爭取時間，選取第一個后的每一個我們希望其都是最優(yōu)的，這樣能節(jié)省一定的時間。假設(shè)有這么一組物品，其大小和價值如下表所示：

物品編號	大小	價值
1	2	1
2	3	4
3	4	3
4	5	6
5	6	8

給我們一個容量為12的背包，讓我們裝上面這些物品，我們可以用下面的方法來解決尋找最優(yōu)組合的問題

建立一個二圍數(shù)組，數(shù)組包括n個行(n為物品數(shù)量)和capcity+1列

首先我們對第一個物品進(jìn)行取舍，因為物品1大小為2，先將物品1加入背包，物品1的大小為2，則cap>=2的時候能容納item1，這時候背包里面物品的價值為item1.Value=1,得到以下數(shù)組

0	1	2	3	4	5	6	7	8	9	10	11	12
0	0	1	1	1	1	1	1	1	1	1	1	1

接下來處理物品1和物品2的子集，item2的大小為3，則只有cap=3的時候才能容納item2,當(dāng)cap=3的時候講好能容納item2,此時背包里面價值item2.value=4,且剩余空間為0，當(dāng)cap=4的時候，能容納item2，且剩余空間為1，不能容item1,當(dāng)cap=5的時候，可以容納item1+item2,此時的價值為1+4 =5，得到第二行

0	1	2	3	4	5	6	7	8	9	10	11	12
0	0	1	4	4	5	5	5	5	5	5	5	5

下面分析物品三，物品二，物品一的子集，物品三的大小為4，當(dāng)cap=4的時候就能容納item3,但此時背包里面的價值為3，明顯小于上一行中的cap=4的價值（3<4),所以cap=4時不能將item3放進(jìn)去，所以第三行的4位置應(yīng)該和第二行的4位置一致，當(dāng)cap=5的時候能夠容納item3,且剩余空間為1，和cap=4情況一樣，拷貝上一行同一位置的值，當(dāng)cap=6，放置item3后剩余2，能容item1和item4,二者的總價值:1+3=4<5，故拷貝上一行同位置的值，cap=7的時候，能容item2+item3，總價值大小為7,大于>5，故cap=8的時的值為7，cap=9的時候仍能容難item3+item2,value=7，cap=8的時候，能容納item1+item2+item3,且總價值大小為8，大于上一行同位置的值，故cap>=9時候，總價值大小為8,第三行：

0	1	2	3	4	5	6	7	8	9	10	11	12
0	0	1	4	4	5	5	7	7	8	8	8	8

按照這樣的邏輯可以得到下面兩列，最后二圍數(shù)組是

0，0，1，1，1，1，1，1，1，1，1，1，1

0，0，1，4，4，5，5，5，5，5，5，5，5

0，0，1，4，4，5，5，7，7，8，8，8，8

0，0，1，4，4，6，6，7，10，10，11，11，13

0，0，1，4，4，6，8，8，10，12，12，14，14

得到這樣的數(shù)組之后，我們需要作的是根據(jù)這個二圍數(shù)組來產(chǎn)生最優(yōu)物品子集，方法為

從第len行開始，比較最后一行cap索引位置的值是否大于上一行同一位置的值，如先比較第五行位置12的值（14）與第四行位置12的值(13)，因為14!=13,所以item5放置到最優(yōu)集合中，item5的大小為6，故比較第四行cap-6=6的位置上的值與上一行同一位置上值得大小，因為6！= 5,所以item4能放置到最優(yōu)集合，下一步要比較的位置cap = 6-item4.Size=6-5=1,第三行位置1與第二行位置1相同，故item3不能放置到最優(yōu)集合，第二行和第一行第一個位置上的值也一樣，所以item2也不能放置進(jìn)去，最后判斷item1是否應(yīng)該在最優(yōu)集合，item5+item4后，剩余空間為1，不能容納item1,故最優(yōu)集合為{item4,item5};

綜合上面的分析，我們可以得到這樣的一個處理流程

1）首先建立一個nx(cap+1)的二圍數(shù)組

2）第一行從嘗試選擇第一個物品開始

3）對于以后的行，對于每個容量1<=cap<=capacity，首先拷貝上一行同一位置的值下來，如果itemi.Size<=cap并且上一行(cap-itemi.Size)位置上的值與itemi.Value的和(tempMax)大于拷貝下來的值的話，就將拷貝下來的值替換為上一行(cap-itemi.Size)位置上的值與itemi.Value的和（tempMax）

4）得到完整數(shù)組之后，我們既可以根據(jù)數(shù)組來確定最優(yōu)集合了，首先從最后一樣最后位置開始，和上一行的同一位置進(jìn)行比較，如果相同，則該行對應(yīng)索引的物品不能放到背包中，否則放到背包，并且開始比較上一行與上上一行在當(dāng)前背包剩余空間索引出的值，如不等，則對應(yīng)物品可放置，如此，直到處理到第二行和第一行的比對完成，然后根據(jù)當(dāng)前背包剩余容量與第一個物品的大小比對來確定物品一是否能放置到背包中

4.源程序
http://xiazai.jb51.net/201606/yuanma/Knapsack(jb51.net).rar

5.結(jié)論

　　上文采用的是動態(tài)編程的方法來處理此類背包問題，上面的文章中兄弟們也提到了用遞歸算法時間復(fù)雜度的問題，認(rèn)為遞歸算法效率比較低下，這種疑問無可厚非，但遞歸算法也有它的優(yōu)點，很多問題都能用遞歸來解決，我目前學(xué)習(xí)的就是用這種算法來解決一些常見問題，對于其他算法，比如此問題也可以采用貪婪算法，遺傳算法等得以更好的解決，但本文暫不作討論，以后有時間，一定將這些算法加以實現(xiàn)并詳細(xì)比較其優(yōu)劣。

您可能感興趣的文章: