欧美大屁股bbbbxxxx,狼人大香伊蕉国产www亚洲,男ji大巴进入女人的视频小说,男人把ji大巴放进女人免费视频,免费情侣作爱视频

歡迎來到入門教程網(wǎng)!

C#教程

當(dāng)前位置:主頁 > 軟件編程 > C#教程 >

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

來源:本站原創(chuàng)|時(shí)間:2020-01-10|欄目:C#教程|點(diǎn)擊: 次

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

網(wǎng)頁制作CMS教程網(wǎng)絡(luò)編程軟件編程腳本語言數(shù)據(jù)庫服務(wù)器

如果侵犯了您的權(quán)利,請(qǐng)與我們聯(lián)系,我們將在24小時(shí)內(nèi)進(jìn)行處理、任何非本站因素導(dǎo)致的法律后果,本站均不負(fù)任何責(zé)任。

聯(lián)系QQ:835971066 | 郵箱:835971066#qq.com(#換成@)

Copyright © 2002-2020 腳本教程網(wǎng) 版權(quán)所有