C#用遞歸算法解決經(jīng)典背包問題
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í)間恐怕早就到了,最終您可能一無所獲,這可不是我們希望的結(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)為遞歸算法效率比較低下,這種疑問無可厚非,但遞歸算法也有它的優(yōu)點(diǎn),很多問題都能用遞歸來解決,我目前學(xué)習(xí)的就是用這種算法來解決一些常見問題,對(duì)于其他算法,比如此問題也可以采用貪婪算法,遺傳算法等得以更好的解決,但本文暫不作討論,以后有時(shí)間,一定將這些算法加以實(shí)現(xiàn)并詳細(xì)比較其優(yōu)劣。
上一篇:深入理解C#中new、override、virtual關(guān)鍵字的區(qū)別
欄 目:C#教程
下一篇:逐步講解快速排序算法及C#版的實(shí)現(xiàn)示例
本文標(biāo)題:C#用遞歸算法解決經(jīng)典背包問題
本文地址:http://mengdiqiu.com.cn/a1/C_jiaocheng/6433.html
您可能感興趣的文章
- 01-10C#實(shí)現(xiàn)判斷當(dāng)前操作用戶管理角色的方法
- 01-10C#使用Dispose模式實(shí)現(xiàn)手動(dòng)對(duì)資源的釋放
- 01-10C#3.0使用EventLog類寫Windows事件日志的方法
- 01-10C#調(diào)用dos窗口獲取相關(guān)信息的方法
- 01-10C#中DataGridView常用操作實(shí)例小結(jié)
- 01-10C#實(shí)現(xiàn)讀取被進(jìn)程占用的文件實(shí)現(xiàn)方法
- 01-10C#禁用雙擊窗體圖標(biāo)關(guān)閉窗體的方法
- 01-10C#使用windows服務(wù)開啟應(yīng)用程序的方法
- 01-10C#線程隊(duì)列用法實(shí)例分析
- 01-10C#利用反射技術(shù)實(shí)現(xiàn)去掉按鈕選中時(shí)的邊框效果


閱讀排行
- 1C語言 while語句的用法詳解
- 2java 實(shí)現(xiàn)簡(jiǎn)單圣誕樹的示例代碼(圣誕
- 3利用C語言實(shí)現(xiàn)“百馬百擔(dān)”問題方法
- 4C語言中計(jì)算正弦的相關(guān)函數(shù)總結(jié)
- 5c語言計(jì)算三角形面積代碼
- 6什么是 WSH(腳本宿主)的詳細(xì)解釋
- 7C++ 中隨機(jī)函數(shù)random函數(shù)的使用方法
- 8正則表達(dá)式匹配各種特殊字符
- 9C語言十進(jìn)制轉(zhuǎn)二進(jìn)制代碼實(shí)例
- 10C語言查找數(shù)組里數(shù)字重復(fù)次數(shù)的方法
本欄相關(guān)
- 01-10C#通過反射獲取當(dāng)前工程中所有窗體并
- 01-10關(guān)于ASP網(wǎng)頁無法打開的解決方案
- 01-10WinForm限制窗體不能移到屏幕外的方法
- 01-10WinForm繪制圓角的方法
- 01-10C#實(shí)現(xiàn)txt定位指定行完整實(shí)例
- 01-10WinForm實(shí)現(xiàn)仿視頻 器左下角滾動(dòng)新
- 01-10C#停止線程的方法
- 01-10C#實(shí)現(xiàn)清空回收站的方法
- 01-10C#通過重寫Panel改變邊框顏色與寬度的
- 01-10C#實(shí)現(xiàn)讀取注冊(cè)表監(jiān)控當(dāng)前操作系統(tǒng)已
隨機(jī)閱讀
- 08-05DEDE織夢(mèng)data目錄下的sessions文件夾有什
- 01-10使用C語言求解撲克牌的順子及n個(gè)骰子
- 01-11ajax實(shí)現(xiàn)頁面的局部加載
- 04-02jquery與jsp,用jquery
- 08-05織夢(mèng)dedecms什么時(shí)候用欄目交叉功能?
- 08-05dedecms(織夢(mèng))副欄目數(shù)量限制代碼修改
- 01-11Mac OSX 打開原生自帶讀寫NTFS功能(圖文
- 01-10SublimeText編譯C開發(fā)環(huán)境設(shè)置
- 01-10delphi制作wav文件的方法
- 01-10C#中split用法實(shí)例總結(jié)