C#用遞歸算法處理經典背包成績。本站提示廣大學習愛好者：（C#用遞歸算法處理經典背包成績）文章只能為提供參考，不一定能成為您想要的結果。以下是C#用遞歸算法處理經典背包成績正文
1.引子
我們人類是一種貪心的植物，假如給您一個容量必定的背包和一些年夜小紛歧的物品，裝到背包外面的物品就歸您，碰到這類功德年夜家必定不會錯過，用力塞紛歧定是最好的方法，用頭腦才行，上面就教您若何處理如許的成績，以取得更多的獎品。
2.運用場景
在一個物品向量中找到一個子集知足前提以下 ：
1）這個子集加起來的體積年夜小不克不及年夜於指定閥值
2）這個物品子集加起來價值年夜小是向量V中一切知足前提1的子集中最年夜的
3.剖析
背包成績有很多多少版本，本文只研討0/1版本，即對一個物體要末選用，要末就擯棄，不克不及將一個物體再持續細分的情形。這類成績最簡略的辦法就是找出這個向量的一切子集，好像找出冪集中的子集一樣，但這類遍歷的辦法生怕其實不會被聰慧的我們所應用，如今舉行這些運動的電視台也異常聰慧，他們不只請求您能將物品裝出來，並且指定操作時光，如許當您漸漸騰騰的裝出來倒出來的時刻，時光生怕早就到了，終究您能夠一無所得，這可不是我們願望的成果，我們須要應用一些戰略：第一次我們可以從年夜小小於背包涵量的物品中隨便挑取一個，如許可以盡可能爭奪時光，拔取第一個後的每個我們願望其都是最優的，如許能節儉必定的時光。假定有這麼一組物品，其年夜小和價值以下表所示：
給我們一個容量為12的背包，讓我們裝下面這些物品，我們可以用上面的辦法來處理尋覓最優組合的成績
樹立一個二圍數組，數組包含n個行(n為物品數目)和capcity+1列
起首我們對第一個物品停止棄取，由於物品1年夜小為2，先將物品1參加背包，物品1的年夜小為2，則cap>=2的時刻能包容item1，這時候候背包外面物品的價值為item1.Value=1,獲得以下數組
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,當cap=3的時刻講好能包容item2,此時背包外面價值item2.value=4,且殘剩空間為0，當cap=4的時刻，能包容item2，且殘剩空間為1，不克不及容item1,當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，當cap=4的時刻就可以包容item3,但此時背包外面的價值為3，顯著小於上一行中的cap=4的價值（3<4),所以cap=4時不克不及將item3放出來，所以第三行的4地位應當和第二行的4地位分歧，當cap=5的時刻可以或許包容item3,且殘剩空間為1，和cap=4情形一樣，拷貝上一行統一地位的值，當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
依照如許的邏輯可以獲得上面兩列，最初二圍數組是
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
獲得如許的數組以後，我們須要作的是依據這個二圍數組來發生最優物品子集，辦法為
從第len行開端，比擬最初一行cap索引地位的值能否年夜於上一行統一地位的值，如先比擬第五行地位12的值（14）與第四行地位12的值(13)，由於14!=13,所以item5放置到最優聚集中，item5的年夜小為6，故比擬第四行cap-6=6的地位上的值與上一行統一地位上值得年夜小，由於6！= 5,所以item4能放置到最優聚集，下一步要比擬的地位cap = 6-item4.Size=6-5=1,第三行地位1與第二行地位1雷同，故item3不克不及放置到最優聚集，第二行和第一行第一個地位上的值也一樣，所以item2也不克不及放置出來，最初斷定item1能否應當在最優聚集，item5+item4後，殘剩空間為1，不克不及包容item1,故最優聚集為{item4,item5};
綜合下面的剖析，我們可以獲得如許的一個處置流程
1）起首樹立一個nx(cap+1)的二圍數組
2）第一行從測驗考試選擇第一個物品開端
3）關於今後的行，關於每一個容量1<=cap<=capacity，起首拷貝上一行統一地位的值上去，假如itemi.Size<=cap而且上一行(cap-itemi.Size)地位上的值與itemi.Value的 和(tempMax)年夜於拷貝上去的值的話，就將拷貝上去的值調換為上一行(cap-itemi.Size)地位上的值與itemi.Value的 和（tempMax）
4）獲得完全數組以後，我們既可以依據數組來肯定最優聚集了，起首從最初一樣最初地位開端，和上一行的統一地位停止比擬，假如雷同，則該行對應索引的物品不克不及放到背包中，不然放到背包，而且開端比擬上一行與 上上一行在以後背包殘剩空間索引出的值，如不等，則對應物品可放置，如斯，直隨處理到第二行和第一行的比對完成，然後依據以後背包殘剩容量與第一個物品的年夜小比對來肯定物品一能否能放置到背包中
4.源法式
http://xiazai.jb51.net/201606/yuanma/Knapsack(jb51.net).rar
5.結論
上文彩用的是靜態編程的辦法來處置此類背包成績，下面的文章中兄弟們也提到了用遞歸算法時光龐雜度的成績，以為遞歸算法效力比擬低下，這類疑問無可厚非，但遞歸算法也有它的長處，許多成績都能用遞歸來處理，我今朝進修的就是用這類算法來處理一些罕見成績，關於其他算法，好比此成績也能夠采取貪心算法，遺傳算法等得以更好的處理，但本文暫不作評論辯論，今後有時光，必定將這些算法加以完成並具體比擬其好壞。
