發(fā)布時間：2018-06-20 09:54

  本文選題：綜合背包 + 貪婪算法��； 參考：《吉林大學》2017年碩士論文

【摘要】：背包問題是一種組合優(yōu)化的NP完全問題。問題可以描述為,給定了一個背包和一組物品,每個物品都有其自己的重量和價值,在背包限定的總重量內,通過選擇部分物品,使得背包的總價值最高。背包問題經常會出現(xiàn)在商業(yè)、組合數(shù)學、密碼學等領域中。0-1背包問題、依賴問題和多背包問題就是在背包問題的概念基礎上擴展應用的NP完全問題,但隨著待解決問題復雜性的提高,傳統(tǒng)的0-1背包問題、依賴問題和多背包問題都已不能表述錯綜復雜的實際問題。本文提出一種在0-1背包問題、依賴問題和多背包問題的理論基礎上附加其它約束條件的復雜的綜合背包問題。綜合背包問題可描述為,給定了一組物品,每個物品都有其自身的重量和度數(shù),度數(shù)由入度和出度相加獲得。物品相互之間存在某種聯(lián)系,例如物品item0依賴item1和item2,則item0的出度數(shù)是2,假設item1也對item0存在依賴關系,在只考慮item1一個依賴關系的條件下,item0的入度數(shù)是1,由此也可以看出度數(shù)是單向計算的。除了給出一組物品外,綜合背包問題并不像傳統(tǒng)的背包問題那樣只給出一個背包,而是存在未知個數(shù)的背包。每個背包的重量容納值都是相同的,此外每個背包的入度和出度數(shù)都是被限制數(shù)量的。背包的入度和出度數(shù)依賴裝進背包的所有物品的入度和出度數(shù)累加。綜合背包問題的解可描述為,在滿足不超過每個背包的總容量和不違反入度和出度數(shù)的限制的情況下,使用最少的背包個數(shù),將所有的物品裝入一組背包中。本文研究了依賴不同貪婪策略選擇的混合貪婪算法計算出綜合背包問題的最終解�；旌县澙匪惴ㄍㄟ^使用不同的貪婪策略計算出輸入值的貪婪因子序列,在滿足局部最優(yōu)解的情形下,以迭代的方式做出相繼的貪心選擇,得到問題的最終解。最后對根據(jù)不同貪婪策略的運用計算出的最終解進行分析,找出依賴貪婪策略的綜合背包問題的最優(yōu)解。
[Abstract]:Knapsack problem is a combinatorial optimization NP complete problem. The problem can be described as that given a knapsack and a group of items, each item has its own weight and value. Within the total weight of the knapsack, by selecting some items, the total value of the knapsack is the highest. Knapsack problem often appears in the fields of business, combinatorial mathematics, cryptography and so on. The dependency problem and multi-knapsack problem are NP-complete problems that extend the application of knapsack problem based on the concept of knapsack problem. However, with the improvement of the complexity of the unsolved problem, the traditional 0-1 knapsack problem, dependency problem and multi-knapsack problem can no longer express complicated practical problems. In this paper, we propose a complex synthetic knapsack problem with other constraints on the basis of the theory of 0-1 knapsack problem, dependency problem and multi-knapsack problem. The comprehensive knapsack problem can be described as: given a set of items, each item has its own weight and degree, and the degree is obtained by the sum of entry and output. There is some connection between items, for example, if the item item0 depends on item1 and item2, then the item0 has a degree of 2, assuming that item1 also has a dependency on item0. Under the condition that only one item1 dependency is considered, the input degree of item0 is 1, and it can be seen that the degree is calculated in one direction. Besides giving a set of items, the synthetic knapsack problem does not give only one knapsack as the traditional knapsack problem, but has an unknown number of knapsack. The weight of each knapsack is the same, in addition to each knapsack's entry and output are limited in number. The entry and output of the knapsack depends on the cumulative entry and output of all items loaded into the backpack. The solution of the synthetic knapsack problem can be described as that, under the condition that the total capacity of each knapsack and the limit of entry and output are not exceeded, all items are packed into a group of knapsack with the least number of knapsack. In this paper, a hybrid greedy algorithm based on the choice of different greedy strategies is studied to calculate the final solution of the synthetic knapsack problem. The hybrid greedy algorithm calculates the greedy factor sequence of the input value by using different greedy strategies. When the local optimal solution is satisfied, successive greedy selection is made iteratively and the final solution of the problem is obtained. Finally, the final solution calculated by different greedy strategies is analyzed to find the optimal solution of the comprehensive knapsack problem which depends on the greedy strategy.
【學位授予單位】：吉林大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TP18

【相似文獻】

相關期刊論文 前10條

1 劉建軍,姜華;編程解決背包問題[J];德州高專學報;2000年04期

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

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

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

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

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

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

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

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

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

相關會議論文 前6條

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

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

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

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

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

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

相關博士學位論文 前2條

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

2 TRUONG KHAC TUNG;[D];湖南大學;2013年

相關碩士學位論文 前10條

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

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

3 包宗藩;風力驅動優(yōu)化算法及其應用研究[D];廣西民族大學;2016年

4 張悅;價值可變的0-1多背包問題模型及其優(yōu)化算法研究[D];北京交通大學;2017年

5 陳烏吉瑪;基于綜合背包問題的混合貪婪算法的研究[D];吉林大學;2017年

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

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

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

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

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

，

本文編號：2043860