本文關(guān)鍵詞：背包問題的動態(tài)規(guī)劃改進算法

  更多相關(guān)文章： 背包問題 動態(tài)規(guī)劃 狀態(tài)表示 決策依賴

【摘要】：在動態(tài)規(guī)劃算法的基礎(chǔ)上提出了改進算法,對于0-1背包問題,改進了動態(tài)規(guī)劃算法的狀態(tài)表示以減少需要計算的狀態(tài)個數(shù)來求解該問題;對于完全背包問題,簡化了動態(tài)規(guī)劃算法狀態(tài)的決策依賴關(guān)系來求解該問題.實驗結(jié)果表明:所提出的改進算法在時空效率上具有一定的有效性和優(yōu)越性.
【作者單位】： 中南民族大學(xué)計算機科學(xué)學(xué)院;
【關(guān)鍵詞】： 背包問題 動態(tài)規(guī)劃 狀態(tài)表示 決策依賴
【基金】：國家自然科學(xué)基金資助項目(71003038)
【分類號】：TP301.6
【正文快照】： 背包問題在現(xiàn)實生活中廣泛地應(yīng)用于需要基于有限資源進行選擇判斷的領(lǐng)域[1],如貨物裝載、投資組合、下料問題等[2],因此對該問題的研究具有重要的實際意義.背包問題可以衍生出0-1背包問題、完全背包問題和多重背包問題等[3].解決0-1背包問題的動態(tài)規(guī)劃算法的時空復(fù)雜度為O(n W

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 何文明,朱起定;背包問題的循環(huán)及并行解[J];湘潭師范學(xué)院學(xué)報(社會科學(xué)版);2000年03期

2 任瑞征,嚴蔚敏;整數(shù)背包問題的應(yīng)用及其算法研究[J];小型微型計算機系統(tǒng);2001年02期

3 葉俊,劉賢德,韓露;基于博弈論的背包問題優(yōu)化算法[J];華中科技大學(xué)學(xué)報(自然科學(xué)版);2003年09期

4 羅小虎,趙雷;一個解決0/1背包問題的蟻群方法[J];蘇州大學(xué)學(xué)報(工科版);2004年01期

5 宋翔,聶義勇,儲誠斌;無限制背包問題的爬山算法[J];小型微型計算機系統(tǒng);2004年07期

6 謝濤,陳火旺,康立山;二次背包問題的一種快速解法[J];計算機學(xué)報;2004年09期

7 王喜鳳;淺析0/1背包問題[J];電腦知識與技術(shù);2004年29期

8 華中生,張斌;求解可分離連續(xù)凸二次背包問題的直接算法[J];系統(tǒng)工程與電子技術(shù);2005年02期

9 宋海洲;魏旭真;;求解0-1背包問題的混合遺傳算法[J];華僑大學(xué)學(xué)報(自然科學(xué)版);2006年01期

10 熊偉清;魏平;王小權(quán);;蟻群算法求解多維0/1背包問題[J];計算機工程與科學(xué);2006年10期

中國重要會議論文全文數(shù)據(jù)庫 前6條

1 喬善平;朱波;趙玲;;基于移動Agent的0-1背包問題分布式求解[A];2008'中國信息技術(shù)與應(yīng)用學(xué)術(shù)論壇論文集（一）[C];2008年

2 高尚;;背包問題的分布估計算法[A];2013年中國智能自動化學(xué)術(shù)會議論文集（第五分冊）[C];2013年

3 徐俊杰;忻展紅;;粒子群優(yōu)化在0/1背包問題中的應(yīng)用[A];中國運籌學(xué)會第七屆學(xué)術(shù)交流會論文集（上卷）[C];2004年

4 姜宇;蘇中濱;鄭萍;;求解O/1背包問題的算法綜述[A];黑龍江省計算機學(xué)會2009年學(xué)術(shù)交流年會論文集[C];2010年

5 劉裴寰;姜青山;王備戰(zhàn);史亮;;基于K均值聚類求解多維背包問題的算法[A];第二十三屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（技術(shù)報告篇）[C];2006年

6 李偉;呂克偉;;類背包DH問題的比特安全性研究[A];第28次全國計算機安全學(xué)術(shù)交流會論文集[C];2013年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前2條

1 黃斌超;限制性多重背包問題的研究[D];云南大學(xué);2015年

2 TRUONG KHAC TUNG;[D];湖南大學(xué);2013年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 史如意;帶流量約束的星型圖背包問題[D];浙江大學(xué);2015年

2 孫飛;改進螢火蟲算法求解0-1背包問題[D];西北師范大學(xué);2015年

3 聶大干;森林優(yōu)化算法的改進及離散化研究[D];蘭州大學(xué);2016年

4 潘夏福;混合蟻群算法求解0-1背包問題[D];廈門大學(xué);2008年

5 朱閱岸;解0-1背包問題的算法比較和改進[D];暨南大學(xué);2011年

6 史今馳;背包問題的實用求解算法研究[D];山東大學(xué);2005年

7 鄭楊凡;基于屬性論的0-1背包問題算法研究[D];上海海事大學(xué);2005年

8 李其;有償在線背包問題的研究[D];大連理工大學(xué);2012年

9 孟曉笑;并行環(huán)境下0-1背包問題的解決策略[D];湖北大學(xué);2011年

10 鐘海林;背包問題的一種新算法：降維遞歸算法[D];江西師范大學(xué);2008年

，

本文編號：889559