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

【摘要】：背包問題是一種組合優(yōu)化的NP完全問題。問題可以描述為,給定了一個(gè)背包和一組物品,每個(gè)物品都有其自己的重量和價(jià)值,在背包限定的總重量?jī)?nèi),通過選擇部分物品,使得背包的總價(jià)值最高。背包問題經(jīng)常會(huì)出現(xiàn)在商業(yè)、組合數(shù)學(xué)、密碼學(xué)等領(lǐng)域中。0-1背包問題、依賴問題和多背包問題就是在背包問題的概念基礎(chǔ)上擴(kuò)展應(yīng)用的NP完全問題,但隨著待解決問題復(fù)雜性的提高,傳統(tǒng)的0-1背包問題、依賴問題和多背包問題都已不能表述錯(cuò)綜復(fù)雜的實(shí)際問題。本文提出一種在0-1背包問題、依賴問題和多背包問題的理論基礎(chǔ)上附加其它約束條件的復(fù)雜的綜合背包問題。綜合背包問題可描述為,給定了一組物品,每個(gè)物品都有其自身的重量和度數(shù),度數(shù)由入度和出度相加獲得。物品相互之間存在某種聯(lián)系,例如物品item0依賴item1和item2,則item0的出度數(shù)是2,假設(shè)item1也對(duì)item0存在依賴關(guān)系,在只考慮item1一個(gè)依賴關(guān)系的條件下,item0的入度數(shù)是1,由此也可以看出度數(shù)是單向計(jì)算的。除了給出一組物品外,綜合背包問題并不像傳統(tǒng)的背包問題那樣只給出一個(gè)背包,而是存在未知個(gè)數(shù)的背包。每個(gè)背包的重量容納值都是相同的,此外每個(gè)背包的入度和出度數(shù)都是被限制數(shù)量的。背包的入度和出度數(shù)依賴裝進(jìn)背包的所有物品的入度和出度數(shù)累加。綜合背包問題的解可描述為,在滿足不超過每個(gè)背包的總?cè)萘亢筒贿`反入度和出度數(shù)的限制的情況下,使用最少的背包個(gè)數(shù),將所有的物品裝入一組背包中。本文研究了依賴不同貪婪策略選擇的混合貪婪算法計(jì)算出綜合背包問題的最終解。混合貪婪算法通過使用不同的貪婪策略計(jì)算出輸入值的貪婪因子序列,在滿足局部最優(yōu)解的情形下,以迭代的方式做出相繼的貪心選擇,得到問題的最終解。最后對(duì)根據(jù)不同貪婪策略的運(yùn)用計(jì)算出的最終解進(jìn)行分析,找出依賴貪婪策略的綜合背包問題的最優(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.
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP18

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

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

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

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

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

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

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

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

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

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

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

相關(guān)會(huì)議論文 前6條

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

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

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

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

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

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

相關(guān)博士學(xué)位論文 前2條

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

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

相關(guān)碩士學(xué)位論文 前10條

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

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

3 包宗藩;風(fēng)力驅(qū)動(dòng)優(yōu)化算法及其應(yīng)用研究[D];廣西民族大學(xué);2016年

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

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

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

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

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

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

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

，

本文編號(hào)：2043860