快捷導(dǎo)航

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

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

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

1.引子

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

2.應(yīng)用場(chǎng)景

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

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

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

3.分析

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

物品編號(hào)	大小	價(jià)值
1	2	1
2	3	4
3	4	3
4	5	6
5	6	8

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

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

首先我們對(duì)第一個(gè)物品進(jìn)行取舍，因?yàn)槲锲?大小為2，先將物品1加入背包，物品1的大小為2，則cap>=2的時(shí)候能容納item1，這時(shí)候背包里面物品的價(jià)值為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的時(shí)候才能容納item2,當(dāng)cap=3的時(shí)候講好能容納item2,此時(shí)背包里面價(jià)值item2.value=4,且剩余空間為0，當(dāng)cap=4的時(shí)候，能容納item2，且剩余空間為1，不能容item1,當(dāng)cap=5的時(shí)候，可以容納item1+item2,此時(shí)的價(jià)值為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的時(shí)候就能容納item3,但此時(shí)背包里面的價(jià)值為3，明顯小于上一行中的cap=4的價(jià)值（3<4),所以cap=4時(shí)不能將item3放進(jìn)去，所以第三行的4位置應(yīng)該和第二行的4位置一致，當(dāng)cap=5的時(shí)候能夠容納item3,且剩余空間為1，和cap=4情況一樣，拷貝上一行同一位置的值，當(dāng)cap=6，放置item3后剩余2，能容item1和item4,二者的總價(jià)值:1+3=4<5，故拷貝上一行同位置的值，cap=7的時(shí)候，能容item2+item3，總價(jià)值大小為7,大于>5，故cap=8的時(shí)的值為7，cap=9的時(shí)候仍能容難item3+item2,value=7，cap=8的時(shí)候，能容納item1+item2+item3,且總價(jià)值大小為8，大于上一行同位置的值，故cap>=9時(shí)候，總價(jià)值大小為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ù)這個(gè)二圍數(shù)組來產(chǎn)生最優(yōu)物品子集，方法為

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

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

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

2）第一行從嘗試選擇第一個(gè)物品開始

3）對(duì)于以后的行，對(duì)于每個(gè)容量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)行比較，如果相同，則該行對(duì)應(yīng)索引的物品不能放到背包中，否則放到背包，并且開始比較上一行與上上一行在當(dāng)前背包剩余空間索引出的值，如不等，則對(duì)應(yīng)物品可放置，如此，直到處理到第二行和第一行的比對(duì)完成，然后根據(jù)當(dāng)前背包剩余容量與第一個(gè)物品的大小比對(duì)來確定物品一是否能放置到背包中

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

5.結(jié)論

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

您可能感興趣的文章: