基于1stOpt的背包問(wèn)題建模與實(shí)驗(yàn)案例設(shè)計(jì)

陳恒杰 張家偉 薛善增

摘? 要? 設(shè)計(jì)11類(lèi)背包問(wèn)題的實(shí)驗(yàn)教學(xué)案例，建立相應(yīng)的數(shù)學(xué)模型，然后利用1stOpt編程進(jìn)行求解。結(jié)果表明：建立的通用數(shù)學(xué)模型正確，設(shè)計(jì)的實(shí)例合理，利用1stOpt編寫(xiě)的背包求解程序有效。與其他軟件或解決背包問(wèn)題的傳統(tǒng)算法相比，1stOpt不僅通用可靠，編程簡(jiǎn)單，具有較快的收斂速度，而且具有良好的全局尋優(yōu)和多解獲取能力。基于1stOpt的編程不僅可快速有效地解決背包問(wèn)題，對(duì)解決運(yùn)籌學(xué)、數(shù)據(jù)結(jié)構(gòu)與算法分析和數(shù)學(xué)建模等相關(guān)問(wèn)題以及相應(yīng)的教學(xué)都具有十分重要的借鑒意義，而且能提高學(xué)生的學(xué)習(xí)興趣，增強(qiáng)學(xué)生的實(shí)踐能力，達(dá)到學(xué)以致用的目的。

關(guān)鍵詞? 1stOpt；背包問(wèn)題；數(shù)學(xué)模型；數(shù)學(xué)建模

中圖分類(lèi)號(hào)：G642.423? ? 文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1671-489X（2022）12-0133-08

Abstract? In this paper， eleven kinds of experimental teaching?cases of knapsack problem were designed， the corresponding mathematical models were established， and then 1stOpt pro-gramming was employed to solve it. The study shows that the general mathematical model established in this paper is?correct and the knapsack solver written by 1stOpt is effective，?the designed examples are reasonable. Compared with other?softwares or traditional algorithms to solve knapsack pro-blems， 1stOpt is not only universal and reliable， but also has?fast convergence speed. At the same time， it has good global optimization and multi-solution acquisition ability. Based on?1stOpt programming can not only solve the knapsack pro-blem quickly and effectively， but also have very important reference significance to solve the related problems such as operational research， data structure and algorithm analysis and mathematical modeling， as well as the corresponding practical teaching. At the same time， it can improve students interest in learning， enhance their practical ability， and achi-eve the aim that put what weve learned to use.

Key words? 1stOpt; knapsack problem; mathematical model; mathematical modeling

0? 引言

背包問(wèn)題是一種典型的組合優(yōu)化問(wèn)題，屬于NP難問(wèn)題，經(jīng)常出現(xiàn)在離散數(shù)學(xué)、密碼學(xué)、計(jì)算復(fù)雜性理論等各類(lèi)科學(xué)研究中[1-2]，在日常工作、生活中更是有著大量的應(yīng)用場(chǎng)景（投資決策、貨物裝箱、資源調(diào)度等）[3-5]，相應(yīng)的考題常見(jiàn)于各大互聯(lián)網(wǎng)企業(yè)的招聘中。背包問(wèn)題的常見(jiàn)求解算法有窮舉法、回溯法、遞歸法、分歧定界法和動(dòng)態(tài)規(guī)劃法等，較難獲得全局最優(yōu)解。近年來(lái)，隨著啟發(fā)式算法的蓬勃發(fā)展，研究者發(fā)展大量的算法并將其應(yīng)用于解決背包問(wèn)題[6-11]，但在實(shí)際應(yīng)用中，這些解決方法往往只能解決特定問(wèn)題，且存在不收斂、強(qiáng)隨機(jī)性、早熟等現(xiàn)象，研究成果基本停留在研究報(bào)告或科學(xué)論文層面，絕大多數(shù)本科生甚至研究生很難掌握其中的算法和編程，更難短時(shí)間內(nèi)解決實(shí)際問(wèn)題。因此，無(wú)論在數(shù)據(jù)結(jié)構(gòu)與算法分析、運(yùn)籌學(xué)還是數(shù)學(xué)建模實(shí)驗(yàn)教學(xué)中，利用上述成果都是比較困難的。

1stOpt由七維高科開(kāi)發(fā)，是一款優(yōu)秀的通用全局優(yōu)化軟件平臺(tái)[12]，具有簡(jiǎn)單易用、穩(wěn)定性好、魯棒性強(qiáng)、全局尋優(yōu)能力出眾等特點(diǎn)。通過(guò)對(duì)美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院（NIST）測(cè)試集的計(jì)算比較，其效率和成功率大大高于同類(lèi)國(guó)際主流軟件（MATLAB、LINGO等）。可以預(yù)見(jiàn)，將1stOpt應(yīng)用到相關(guān)實(shí)驗(yàn)教學(xué)中，不僅能降低學(xué)生解決問(wèn)題的難度，提高學(xué)生解決問(wèn)題的能力，而且能激發(fā)學(xué)生的學(xué)習(xí)興趣，達(dá)到學(xué)以致用的目的。然而，截至目前還未看到任何有關(guān)將1stOpt應(yīng)用到運(yùn)籌學(xué)和數(shù)學(xué)建模課程的報(bào)道[13]。本文以多個(gè)常見(jiàn)背包問(wèn)題為例，探索將1stOpt引入運(yùn)籌學(xué)實(shí)驗(yàn)教學(xué)，力圖總結(jié)一套適合相關(guān)教學(xué)的方法與經(jīng)驗(yàn)，進(jìn)而增強(qiáng)運(yùn)籌學(xué)、數(shù)學(xué)建模等相關(guān)課程的教學(xué)體驗(yàn)和教學(xué)效果。

1? 背包問(wèn)題的數(shù)學(xué)模型及其1stOpt實(shí)現(xiàn)

1.1? 0-1背包問(wèn)題

【定義】設(shè)有n類(lèi)物品，質(zhì)量分別為ωi，價(jià)值依次為ci，每類(lèi)物品僅一件，有一最大承重為W的背包，如何裝包才能使背包中物品的價(jià)值最大？

【分析】是否向背包裝入第i件物品用xi表示，1表示裝入，0表示不裝入，則上述問(wèn)題可用以下數(shù)學(xué)模型描述：

【例1】有質(zhì)量分別是1、2、6、5、4、3、3、2，相應(yīng)價(jià)值為6、8、7、4、6、1、2、3的8件物品，現(xiàn)有一承重為20的背包，如何讓背包里裝入的物品具有最大的價(jià)值總和？

表1所示程序使用線性規(guī)劃算法（LP），參數(shù)為具有邏輯屬性的BinParameter，其值取0或1，1stOpt共迭代兩次，耗時(shí)不足10微秒，得到的最優(yōu)背包方案為x1=1，x2=1，x3=1，x4=1，x5=1，x6=0，x7=0，x8=1，此時(shí)背包載重剛好20，價(jià)值總和為34。為檢驗(yàn)該解是否為全局最優(yōu)解，若是全局最優(yōu)解又是否為唯一最優(yōu)方案，注釋掉程序中的算法部分，在圖1所示的主要設(shè)置中選擇最大繼承法（MIO），在選項(xiàng)一中選擇多解輸出和多重運(yùn)算，其中多重運(yùn)算設(shè)置到50。計(jì)算結(jié)果顯示：50次運(yùn)算均為上述同一解，說(shuō)明34為該問(wèn)題的唯一全局最優(yōu)解。

1.2? 完全背包問(wèn)題

【定義】設(shè)有n類(lèi)物品，質(zhì)量分別為ωi，價(jià)值依次為ci，每類(lèi)物品無(wú)限多，有一最大承重為W的背包，如何裝包才能使背包中物品的價(jià)值最大？

【分析】設(shè)向背包裝入第i件物品的件數(shù)用xi表示，xi為零和正整數(shù)構(gòu)成的自然數(shù)N，則上述問(wèn)題可歸結(jié)為以下數(shù)學(xué)模型：

【例2】現(xiàn)有質(zhì)量分別是2、3、5、7，價(jià)值為1、3、5、9的4類(lèi)物品，每類(lèi)物品數(shù)量無(wú)限個(gè)，現(xiàn)有一承重為10的背包，如何讓背包里裝入的物品具有最大的價(jià)值總和？

如表2所示，與0-1整數(shù)規(guī)劃不同，程序中的BinParameter變成IntParameter，IntParameter被默認(rèn)為大于等于0的正整數(shù)。除特別聲明，后續(xù)計(jì)算均設(shè)置為MIO算法，使用多重輸出功能，采用50次多重運(yùn)算。

結(jié)果顯示最優(yōu)解為：x2=1，x4=1。此時(shí)最大價(jià)值為12。若改變最大承重為18，解為x2=1，x4=2，

相應(yīng)價(jià)值為21；最大承重為21時(shí)，x4=3，價(jià)值為27；最大承重為93時(shí)，x1=1，x4=13，價(jià)值為118。上述多種承重下的最優(yōu)解均為唯一解。

1.3? 多重背包問(wèn)題

【定義】設(shè)有n類(lèi)物品，質(zhì)量分別為ωi，價(jià)值依次為ci，每類(lèi)物品有限多，背包最大承重為W，如何裝載使背包物品的價(jià)值最大？

【分析】設(shè)向背包裝入第i件物品的件數(shù)用xi表示，xi為自然數(shù)，bi為各類(lèi)物品的數(shù)目上限，則上述問(wèn)題歸結(jié)為以下數(shù)學(xué)模型：

【例3】質(zhì)量分別是2、6、3、4、5，價(jià)值為10、6、15、8、6的3類(lèi)物品，它們的數(shù)目分別是6、5、2、4、8，現(xiàn)有一承重為12的背包，如何讓背包里裝入的物品具有最大的價(jià)值總和？

多重背包問(wèn)題程序如表3所示。結(jié)果為：x1=3，x3=2，或x1=6，兩個(gè)價(jià)值為60的最優(yōu)解，此時(shí)背包均達(dá)到最大12的承重。

1.4? 二維背包問(wèn)題

【定義】設(shè)有n類(lèi)物品，質(zhì)量和體積分別為ωi和vi，價(jià)值依次為ci，每類(lèi)物品僅一件，背包最大承重為W，最大容積為V，如何裝載使背包物品價(jià)值最大？

【分析】設(shè)是否向背包裝入第i件物品用xi表示，1表示裝入，0表示不裝入，則上述問(wèn)題可用以下數(shù)學(xué)模型描述：

【例4】某人開(kāi)卡車(chē)從外地販貨物回本省銷(xiāo)售，當(dāng)前有4個(gè)貨物：A貨物，質(zhì)量120，體積2，價(jià)值2；B貨物，質(zhì)量155，體積3，價(jià)值5；C貨物，質(zhì)量80，體積2，價(jià)值6；D貨物，質(zhì)量60，體積4，價(jià)值8。該車(chē)最大載重300，最大體積可以裝13，求滿足條件時(shí)能販回的最大價(jià)值。

二維背包問(wèn)題程序如表4所示。當(dāng)x1=0，x2=1，x3=1，x4=1時(shí)，有最大價(jià)值為19，此時(shí)物品質(zhì)量為295，體積為9，此解為唯一最優(yōu)解。

1.5? 混合背包問(wèn)題

【定義】設(shè)有n類(lèi)物品，質(zhì)量和體積分別為ωi和vi，價(jià)值依次為ci，bi為物品各自的數(shù)目，背包最大承重為W，最大容積為V。如何裝載使背包物品的價(jià)值最大？

【分析】據(jù)題意，此為二維混合背包問(wèn)題，設(shè)向背包裝入第i件物品的件數(shù)用xi表示，xi為自然數(shù)，其數(shù)學(xué)模型如下：

【例5】與例4相比，若換成中型卡車(chē)，最大載重和最大體積變?yōu)? 000和30，A、B、C、D貨物數(shù)量為20、50、40、30，則程序可改寫(xiě)為表5所示。

有唯一最優(yōu)解x3=15被找到，此時(shí)最大價(jià)值為90，對(duì)應(yīng)體積為30，質(zhì)量為1 200。

1.6? 部分背包問(wèn)題

【定義】有n個(gè)可分割成任意大小的物品，質(zhì)量和價(jià)值依次為ωi和ci，最大承重為W，如何裝配才能使總價(jià)值最大？

【分析】據(jù)題意，先算出單位價(jià)值并從大到小排序，選擇性價(jià)比最高的，依次放入背包，超重不放，不超就繼續(xù)放入，直到判斷完所有物品，最后沒(méi)填滿部分可以選擇剩余最大性價(jià)比物品的部分，即xi為[0，1]之間的一實(shí)數(shù)。然而，對(duì)于此類(lèi)問(wèn)題，上述排序可以省略，1stOpt會(huì)自動(dòng)將性價(jià)比最優(yōu)的先排，接著判斷次優(yōu)的是否應(yīng)全取，實(shí)際上是將原來(lái)的整數(shù)優(yōu)化問(wèn)題轉(zhuǎn)化為一實(shí)數(shù)問(wèn)題，最終數(shù)學(xué)描述如下：

【例6】如表6所示，有一個(gè)背包，背包承重是W=150，有7個(gè)物品，物品可以分割成任意大小，要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過(guò)總?cè)萘俊?/p>

部分背包（轉(zhuǎn)化到0-1間的實(shí)數(shù)背包）問(wèn)題程序如表7所示。因本問(wèn)題為實(shí)數(shù)優(yōu)化，采用更適合的通用全局優(yōu)化算法（UGO），計(jì)算結(jié)果為：x1=0，x2=1，x3=0，x4=1，x5=0.875，x6=1，x7=1，最大價(jià)值為190.625。

1.7? 多背包問(wèn)題

【定義】給定n個(gè)物品，每個(gè)物品僅有一個(gè)，其價(jià)值為ci，質(zhì)量為ωi；現(xiàn)有m個(gè)背包，每個(gè)背包的承重為di，每個(gè)物品只能取一次，求能獲得的最大價(jià)值。

【分析】xij表示第j個(gè)物品是否選取在第i個(gè)背包中，為二維邏輯變量，其值取0或1，0表示不選取，1表示選取。為便于分析，建立如表8所示的邏輯矩陣幫助理解。Σj≤1表示每件物品的總件數(shù)約束，Σcj*xij表示背包承重約束。若變化Σj≤1中的1為某自然數(shù)，則問(wèn)題轉(zhuǎn)化為多重混合多背包問(wèn)題，不限制則變?yōu)闊o(wú)界混合多背包問(wèn)題。

據(jù)此，該問(wèn)題可用以下數(shù)學(xué)模型描述：

【例7】某人從某地旅游回來(lái)，欲帶回價(jià)值為16、20、32、42、81、30、22、9、60、105的10種土產(chǎn)品，每個(gè)產(chǎn)品的質(zhì)量為10、8、6、7、3、7、1、9、5、12，但因其攜帶的3個(gè)包載重有限，分別為15、18、21，該人如何選擇，才能帶回最大價(jià)值的物品？

多背包問(wèn)題程序如表9所示。該人可帶回的最大價(jià)值為392，可選方案較多，這里僅給出一種：x14=1，x16=1，x23=1，x25=1，x27=1，x29=1，x32=1，x3，10=1。

1.8? 0-1分組背包問(wèn)題

【定義】有n件物品和一個(gè)容量為V的背包，第i件物品的質(zhì)量是ωi，價(jià)值是ci。這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。將哪些物品裝入背包，可使這些物品的質(zhì)量總和不超過(guò)背包容量，且價(jià)值總和最大？

【例8】戰(zhàn)士可從12種質(zhì)量如下的物品中選擇，[{2，3，5，1}，{2，4}，{9，8，2}，15，6，7]，其中1、2、3、4位置處為食品，必且僅選一種；5、6處為飲品，必且只選一種；7、8、9為單兵裝備，必且只選一種；10、11、12位置任意。現(xiàn)有最大負(fù)重為29的士兵，如何選擇，士兵的負(fù)重最大？

【分析】目標(biāo)函數(shù)為使負(fù)重最大，約束為士兵的最大負(fù)重，每個(gè)分組中只能選一種。設(shè)物品是否被選擇變量為xi，被選擇時(shí)為1，不被選擇時(shí)為0，為方便編程，可將上述模型寫(xiě)成簡(jiǎn)便形式：

分組背包問(wèn)題程序如表10所示。有多組目標(biāo)最大值為29的解，分別為：x2=1，x6=1；x7=1；x11=

1，x12=1；x3=1，x5=1；x7=1；x11=1，x12=1；x1=1，x6=

1；x9=1；x10=1，x11=1；x1=1，x6=1；x8=1；x10=1；

……

1.9? 依賴背包問(wèn)題

【定義】給定n類(lèi)物品，每個(gè)物品只有一件，其價(jià)值為ci，質(zhì)量為wi。有個(gè)承重為W的背包，若選了物品i，必須選物品j，表示物品i依賴于物品j。求能獲得的最大價(jià)值。

【例9】按專(zhuān)業(yè)培養(yǎng)方案和個(gè)人規(guī)劃，某學(xué)生欲從高等數(shù)學(xué)、線性代數(shù)、應(yīng)用統(tǒng)計(jì)、大數(shù)據(jù)概論、數(shù)學(xué)建模、大學(xué)物理、計(jì)算機(jī)基礎(chǔ)、大學(xué)語(yǔ)文、體育、大學(xué)英語(yǔ)中選擇最少19個(gè)學(xué)分，上述課程學(xué)分依次為6、2、4、1、2、3、2、2、1、2。高等數(shù)學(xué)是大學(xué)物理的先修課程，數(shù)學(xué)建模的先修課程為高等數(shù)學(xué)和線性代數(shù)，線性代數(shù)的先修課程為高等數(shù)學(xué)，大數(shù)據(jù)概論的先修課程為應(yīng)用統(tǒng)計(jì)。如何選擇，才能既滿足19學(xué)分的最低要求，也不太浪費(fèi)學(xué)分？

【分析】依題意，假定各門(mén)課程學(xué)分ci（i=1…10）為價(jià)值變量，xi為0-1決策變量，1表示選擇，0表示不選擇。高等數(shù)學(xué)（x1）是大學(xué)物理（x6）的先修課程，表明：可單獨(dú)選擇高等數(shù)學(xué)而不選擇大學(xué)物理，即x1=1，x6=0；選擇大學(xué)物理的同時(shí)必須選擇高等數(shù)學(xué)，即x1=1，x6=1；綜合起來(lái)，只要滿足x6≤x1，兩種選擇可能都能滿足。同理，由數(shù)學(xué)建模、線性代數(shù)和高等數(shù)學(xué)的先修關(guān)系，可得約束關(guān)系：x5≤x2≤x1。由大數(shù)據(jù)概論和應(yīng)用統(tǒng)計(jì)的先修關(guān)系，可得x4 ≤x3。最終有如下數(shù)學(xué)模型：

依賴背包問(wèn)題程序如表11所示。有至少18種學(xué)分為19的方案被獲得，這里給出其中4種：x1=

1，x2=1，x3=1，x4=1，x5=1，x7=1，x10=1；x1=1，x2=

1，x3=1，x5=1，x7=1，x9=1，x10=1；x1=1，x3=1，x4=

1，x6=1，x8=1，x9=1，x10=1；x1=1，x2=1，x3=1，x4=

1，x7=1，x8=1，x10=1。

若上述問(wèn)題變?yōu)閺闹腥芜x7門(mén)課程，可獲得的最大學(xué)分為多少？

依賴背包問(wèn)題的變化程序如表12所示。可獲得的最大學(xué)分為21，共獲得4種選擇方案：x1=1，x2=1，x3=1，x6=1，x7=1，x8=1，x10=1；x1=1，x2=1，x3=1，x5=1，x6=1，x7=1，x10=1；x1=1，x2=1，x3=1，x5=1，x6=1，x8=1，x10=1；x1=1，x2=1，x3=1，x5=1，x6=1，x7=1，x8=1。

1.10? 泛化背包

【定義】物品沒(méi)有固定的價(jià)值，其價(jià)值隨分配不同而發(fā)生變化，即泛化物品的概念。

【例10】工廠有3種產(chǎn)品待生產(chǎn)，由于工人對(duì)產(chǎn)品的熟悉程度、耐受極限等不同，造成隨時(shí)間變化每件產(chǎn)品生產(chǎn)時(shí)間也有所不同。某工人對(duì)3種產(chǎn)品的加工總時(shí)間的變化規(guī)律：aixbi。其中ai依次為[2，1，3]，bi分別為[1，2，1]。現(xiàn)要求從這3種產(chǎn)品中完成6件，如何安排，才能使總花費(fèi)時(shí)間最短？

【分析】本例中的時(shí)間可理解為價(jià)值、生產(chǎn)產(chǎn)品的時(shí)間不固定，屬于泛化背包問(wèn)題，程序如表13所示。假設(shè)從某種產(chǎn)品中選出xi件，則上述問(wèn)題可轉(zhuǎn)化為以下數(shù)學(xué)模型：

共找到4個(gè)最優(yōu)解為11的方案，分別是：x1=

4，x2=1，x3=1；x1=3，x2=1，x3=2；x1=1，x2=1，x3=2；

x1=2，x2=1，x3=3。

1.11? 背包問(wèn)題的變化

【定義】上述背包問(wèn)題都是在背包質(zhì)量、容量等限制下，使價(jià)值最大化，可以改變問(wèn)題的提法，如在給定運(yùn)量下求所需最小背包數(shù)等。

【例11】某公司承運(yùn)一批物品，質(zhì)量分別為26、30、40、56、60、76，相應(yīng)需求數(shù)量分別為2、10、8、16、80、6，承重600的背包最少需要多少個(gè)？

【分析】總質(zhì)量Σwi*bi=6 824，理想情況下，假設(shè)k=總質(zhì)量/600為整數(shù)，且背包沒(méi)有任何浪費(fèi)，則k個(gè)包恰好能裝滿要求的總承重，此時(shí)k個(gè)背包為最佳選擇。實(shí)際情況k=總質(zhì)量/600往往不一定為整數(shù)（此時(shí)為11.37），則表明k個(gè)背包肯定不能滿足最小承重，最優(yōu)的情況也只能k+1個(gè)背包（即12個(gè)），即對(duì)k向上取整。即便如此，存在k+1也不能滿足要求的概率，此時(shí)繼續(xù)增加背包個(gè)數(shù)至k+2，依次類(lèi)推，直至問(wèn)題解決，則該問(wèn)題轉(zhuǎn)化為一個(gè)整數(shù)問(wèn)題。其數(shù)學(xué)模型如下：

變化后的背包問(wèn)題程序如表14所示。經(jīng)過(guò)兩次迭代后，找到最大值6 824，和總質(zhì)量一致，因此，12個(gè)背包可以滿足。

背包問(wèn)題變化多樣，其他背包問(wèn)題還包括0-1折扣背包問(wèn)題、動(dòng)態(tài)背包問(wèn)題、隨機(jī)背包問(wèn)題、單連續(xù)變量0-1背包問(wèn)題、二次背包問(wèn)題和多選擇背包問(wèn)題等，鑒于篇幅，這里不再一一舉例。

2? 結(jié)束語(yǔ)

首先給出11類(lèi)背包問(wèn)題的描述，通過(guò)分析建立相應(yīng)問(wèn)題的數(shù)學(xué)模型，接著構(gòu)建適合運(yùn)籌學(xué)教學(xué)的相關(guān)例題，再通過(guò)1stOpt編程，實(shí)現(xiàn)這些問(wèn)題的求解，最后對(duì)結(jié)果進(jìn)行簡(jiǎn)單討論。可以看出，1stOpt在解決背包問(wèn)題時(shí)優(yōu)化效果良好，輕松獲得全局最優(yōu)解；計(jì)算效率超高，可用極短時(shí)間得到最優(yōu)解；編程極其簡(jiǎn)單，同時(shí)能讓學(xué)生深刻理解背包問(wèn)題的精髓，而不是深陷于各類(lèi)算法而忘記解決問(wèn)題的初衷。筆者相信，1stOpt對(duì)背包問(wèn)題的解決過(guò)程（定義、數(shù)學(xué)模型、引例、分析、1stOpt編程、結(jié)果與討論）不僅對(duì)運(yùn)籌學(xué)、數(shù)值優(yōu)化、數(shù)據(jù)結(jié)構(gòu)與分析和數(shù)學(xué)建模等各類(lèi)涉及優(yōu)化或規(guī)劃的教學(xué)具有指導(dǎo)意義，而且對(duì)實(shí)際問(wèn)題的解決同樣具有借鑒意義。

參考文獻(xiàn)

[1] 賀毅朝，王熙熙，張新祿，等.基于離散差分演化的KPC問(wèn)題降維建模與求解[J].計(jì)算機(jī)學(xué)報(bào)，2019，42（10）：2267-2280.

[2] 張平原，蔣瀚，蔡杰，等.格密碼技術(shù)近期研究進(jìn)展?[J].計(jì)算機(jī)研究與發(fā)展，2017，54（10）：2121-2129.

[3] 蘆娟，夏揚(yáng)坤，鄒安全，等.帶裝載能力的需求依背包拆分車(chē)輛路徑問(wèn)題[J].工業(yè)工程，2019，22（6）：67-73.

[4] 趙瑞嘉.遠(yuǎn)海大型維修保障船船型選擇及維修設(shè)備配置方案優(yōu)化研究[D].遼寧：大連海事大學(xué)，2021.

[5] 彭鈺瑩，王剛，牟建紅，等.基于完全背包模型的多列車(chē)優(yōu)化協(xié)同控制研究[J].交通節(jié)能與環(huán)保，2020，16（5）：148-158.

[6] García J， Maureira C. A KNN quantum cuckoo searchalgorithm applied to the multidimensional??knapsack problem[J].Applied Soft Computing.2021（102）：107077.

[7] Marina A. Medvedeva， Vasilios N. et al. Randomized time‐varying knapsack problems via binary??beetle antennae search algorithm： Emphasis on applications in portfolio insurance[J].Mathematical Methods in the Applied Sciences，2021，44（2）：2002-2012.

[8] 徐小平，徐麗，王峰，等.基于Lagrange插值的學(xué)習(xí)猴群算法求解折扣{0-1}背包問(wèn)題[J].計(jì)算機(jī)應(yīng)用，2020，40（11）：3113-3118.

[9] Wei Zequn， Hao JinKao. Kernel based tabu search?for the Set-union Knapsack Problem[J].Expert?Systems with Applications，2021（165）：113802.

[10] 何妙妙.改進(jìn)的細(xì)菌覓食優(yōu)化算法及其在0-1背包問(wèn)題中的應(yīng)用[D].重慶：西南大學(xué)，2020.

[11] 楊新木，楊靜，殷志祥，等.DNA折紙術(shù)在0-1背包問(wèn)題中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，2021，38（3）：777-781.

[12] 程先云，程培澄，程培聰，等.優(yōu)化擬合建模：1stOpt應(yīng)用詳解[M].2版.北京：中國(guó)建材工業(yè)出版社，2019.

[13] 李春，劉澤民，陳恒杰，等.PeakFit、1stOpt在弗蘭克-赫茲實(shí)驗(yàn)數(shù)據(jù)處理中的應(yīng)用[J].大學(xué)物理實(shí)驗(yàn)，2018，31（5）：117-123.