北郵算法設(shè)計(jì)--背包問題實(shí)驗(yàn)報(bào)告

ID:20459988

大?。?29.86 KB

頁數(shù):20頁

時(shí)間:2018-10-10

北郵算法設(shè)計(jì)--背包問題實(shí)驗(yàn)報(bào)告_第1頁
北郵算法設(shè)計(jì)--背包問題實(shí)驗(yàn)報(bào)告_第2頁
北郵算法設(shè)計(jì)--背包問題實(shí)驗(yàn)報(bào)告_第3頁
北郵算法設(shè)計(jì)--背包問題實(shí)驗(yàn)報(bào)告_第4頁
北郵算法設(shè)計(jì)--背包問題實(shí)驗(yàn)報(bào)告_第5頁
資源描述:

《北郵算法設(shè)計(jì)--背包問題實(shí)驗(yàn)報(bào)告》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、一.實(shí)驗(yàn)小組成員:二.實(shí)驗(yàn)內(nèi)容:利用動(dòng)態(tài)規(guī)劃算法解決0-1背問題:要求1:算出最優(yōu)解,給出最優(yōu)組合。實(shí)現(xiàn)基本算法,調(diào)試成功;實(shí)現(xiàn)改進(jìn)算法,調(diào)試成功。三.算法實(shí)現(xiàn)a)動(dòng)態(tài)規(guī)劃算法://不放物品時(shí),價(jià)值都力0;for(intzero=1;zero

2、[weightth]=f[object-1][weightth];//記錄當(dāng)前背包里的重S及價(jià)值,即第object個(gè)物品還未裝下一個(gè)物//品時(shí)的背包的價(jià)值等于第object-1個(gè)物品裝入后背包的價(jià)值if(weightth>=w[object]&&f[object-1][weightth-w[object]]+v[object]>f[object][weightth])f[object][weightth]=f[object-l][weightth-w[object]]+v[object];}//產(chǎn)生最佳方案for(obj

3、ect=number;object>0;-object){if(ffobject][capability!!=ffobject-11[capability])//不相等吋,可知第object個(gè)物品放入了背包{path.push(wfobjectl);//添加最優(yōu)解capability-=w[object];}}b)改進(jìn)算法:voidclear(li$t&self){list::iteratorp=self.begin();list::iteratore=self.end()

4、;list::iteratorn=p;++n;while(n!=e)f(p->second>=n->second)self.erase(n);n=p;++n;}else{++P;++n;}}}voidsort(list&selflist,list&end)"將selflist和other合并為end{1ist::iteratorsl=selflist.begin();list:iteratorel=sel

5、flist.end();list:iterators2=other.begin();list::iteratore2=other.end();while(sl!=el&&s2!=e2)intwin(2);if(sl->firstfirstfirst)win=1;if(s2-〉first〉capability)win=0;if(l==win){end.push_back(*s1);++sl;}elseif(2==win){end.push_back

6、(*s2);++s2;}else{++sl;++s2;}}if(sl==el)while(s2!=e2)if(s2->first<=capability)end.push_back(*s2);++s2;}}else{while(sl!=el){if(sl->first::iterators=self.begin();list::it

7、eratore=self.end();-e;while(e!=s&&e->first>=w)if(e-〉first==w&&e-〉second==v)return1;-e;}if(e->first==w&&e->second==v)return1;return0;}一.實(shí)驗(yàn)程序1、”o-r背包問題的動(dòng)態(tài)規(guī)劃#defineMAXN100//最人物品數(shù)量#defineMAXV500//最大容量intfTMAXN+lirMAXV+11;intw[MAXN+1],v[MAXN+1];//重量和價(jià)值#include

8、m>#includeusingnamespacestd;voidmain()intweight;intvalue;intnumber;intcapability;stackpath;cout?”請(qǐng)輸入物品總數(shù)以及背包容量”<

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無此問題,請(qǐng)放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請(qǐng)聯(lián)系客服處理。

关闭