基于1stOpt的背包問題建模與實驗案例設計

陳恒杰 張家偉 薛善增

摘? 要? 設計11類背包問題的實驗教學案例，建立相應的數學模型，然后利用1stOpt編程進行求解。結果表明：建立的通用數學模型正確，設計的實例合理，利用1stOpt編寫的背包求解程序有效。與其他軟件或解決背包問題的傳統算法相比，1stOpt不僅通用可靠，編程簡單，具有較快的收斂速度，而且具有良好的全局尋優和多解獲取能力。基于1stOpt的編程不僅可快速有效地解決背包問題，對解決運籌學、數據結構與算法分析和數學建模等相關問題以及相應的教學都具有十分重要的借鑒意義，而且能提高學生的學習興趣，增強學生的實踐能力，達到學以致用的目的。

關鍵詞? 1stOpt；背包問題；數學模型；數學建模

中圖分類號：G642.423? ? 文獻標識碼：B

文章編號：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? 引言

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

1stOpt由七維高科開發，是一款優秀的通用全局優化軟件平臺[12]，具有簡單易用、穩定性好、魯棒性強、全局尋優能力出眾等特點。通過對美國國家標準與技術研究院（NIST）測試集的計算比較，其效率和成功率大大高于同類國際主流軟件（MATLAB、LINGO等）。可以預見，將1stOpt應用到相關實驗教學中，不僅能降低學生解決問題的難度，提高學生解決問題的能力，而且能激發學生的學習興趣，達到學以致用的目的。然而，截至目前還未看到任何有關將1stOpt應用到運籌學和數學建模課程的報道[13]。本文以多個常見背包問題為例，探索將1stOpt引入運籌學實驗教學，力圖總結一套適合相關教學的方法與經驗，進而增強運籌學、數學建模等相關課程的教學體驗和教學效果。

1? 背包問題的數學模型及其1stOpt實現

1.1? 0-1背包問題

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

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

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

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

1.2? 完全背包問題

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

【分析】設向背包裝入第i件物品的件數用xi表示，xi為零和正整數構成的自然數N，則上述問題可歸結為以下數學模型：

【例2】現有質量分別是2、3、5、7，價值為1、3、5、9的4類物品，每類物品數量無限個，現有一承重為10的背包，如何讓背包里裝入的物品具有最大的價值總和？

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

結果顯示最優解為：x2=1，x4=1。此時最大價值為12。若改變最大承重為18，解為x2=1，x4=2，

相應價值為21；最大承重為21時，x4=3，價值為27；最大承重為93時，x1=1，x4=13，價值為118。上述多種承重下的最優解均為唯一解。

1.3? 多重背包問題

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

【分析】設向背包裝入第i件物品的件數用xi表示，xi為自然數，bi為各類物品的數目上限，則上述問題歸結為以下數學模型：

【例3】質量分別是2、6、3、4、5，價值為10、6、15、8、6的3類物品，它們的數目分別是6、5、2、4、8，現有一承重為12的背包，如何讓背包里裝入的物品具有最大的價值總和？

多重背包問題程序如表3所示。結果為：x1=3，x3=2，或x1=6，兩個價值為60的最優解，此時背包均達到最大12的承重。

1.4? 二維背包問題

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

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

【例4】某人開卡車從外地販貨物回本省銷售，當前有4個貨物：A貨物，質量120，體積2，價值2；B貨物，質量155，體積3，價值5；C貨物，質量80，體積2，價值6；D貨物，質量60，體積4，價值8。該車最大載重300，最大體積可以裝13，求滿足條件時能販回的最大價值。

二維背包問題程序如表4所示。當x1=0，x2=1，x3=1，x4=1時，有最大價值為19，此時物品質量為295，體積為9，此解為唯一最優解。

1.5? 混合背包問題

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

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

【例5】與例4相比，若換成中型卡車，最大載重和最大體積變為2 000和30，A、B、C、D貨物數量為20、50、40、30，則程序可改寫為表5所示。

有唯一最優解x3=15被找到，此時最大價值為90，對應體積為30，質量為1 200。

1.6? 部分背包問題

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

【分析】據題意，先算出單位價值并從大到小排序，選擇性價比最高的，依次放入背包，超重不放，不超就繼續放入，直到判斷完所有物品，最后沒填滿部分可以選擇剩余最大性價比物品的部分，即xi為[0，1]之間的一實數。然而，對于此類問題，上述排序可以省略，1stOpt會自動將性價比最優的先排，接著判斷次優的是否應全取，實際上是將原來的整數優化問題轉化為一實數問題，最終數學描述如下：

【例6】如表6所示，有一個背包，背包承重是W=150，有7個物品，物品可以分割成任意大小，要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。

部分背包（轉化到0-1間的實數背包）問題程序如表7所示。因本問題為實數優化，采用更適合的通用全局優化算法（UGO），計算結果為：x1=0，x2=1，x3=0，x4=1，x5=0.875，x6=1，x7=1，最大價值為190.625。

1.7? 多背包問題

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

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

據此，該問題可用以下數學模型描述：

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

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

1.8? 0-1分組背包問題

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

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

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

分組背包問題程序如表10所示。有多組目標最大值為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? 依賴背包問題

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

【例9】按專業培養方案和個人規劃，某學生欲從高等數學、線性代數、應用統計、大數據概論、數學建模、大學物理、計算機基礎、大學語文、體育、大學英語中選擇最少19個學分，上述課程學分依次為6、2、4、1、2、3、2、2、1、2。高等數學是大學物理的先修課程，數學建模的先修課程為高等數學和線性代數，線性代數的先修課程為高等數學，大數據概論的先修課程為應用統計。如何選擇，才能既滿足19學分的最低要求，也不太浪費學分？

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

依賴背包問題程序如表11所示。有至少18種學分為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。

若上述問題變為從中任選7門課程，可獲得的最大學分為多少？

依賴背包問題的變化程序如表12所示。可獲得的最大學分為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? 泛化背包

【定義】物品沒有固定的價值，其價值隨分配不同而發生變化，即泛化物品的概念。

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

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

共找到4個最優解為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? 背包問題的變化

【定義】上述背包問題都是在背包質量、容量等限制下，使價值最大化，可以改變問題的提法，如在給定運量下求所需最小背包數等。

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

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

變化后的背包問題程序如表14所示。經過兩次迭代后，找到最大值6 824，和總質量一致，因此，12個背包可以滿足。

背包問題變化多樣，其他背包問題還包括0-1折扣背包問題、動態背包問題、隨機背包問題、單連續變量0-1背包問題、二次背包問題和多選擇背包問題等，鑒于篇幅，這里不再一一舉例。

2? 結束語

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

參考文獻

[1] 賀毅朝，王熙熙，張新祿，等.基于離散差分演化的KPC問題降維建模與求解[J].計算機學報，2019，42（10）：2267-2280.

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

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

[4] 趙瑞嘉.遠海大型維修保障船船型選擇及維修設備配置方案優化研究[D].遼寧：大連海事大學，2021.

[5] 彭鈺瑩，王剛，牟建紅，等.基于完全背包模型的多列車優化協同控制研究[J].交通節能與環保，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插值的學習猴群算法求解折扣{0-1}背包問題[J].計算機應用，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] 何妙妙.改進的細菌覓食優化算法及其在0-1背包問題中的應用[D].重慶：西南大學，2020.

[11] 楊新木，楊靜，殷志祥，等.DNA折紙術在0-1背包問題中的應用[J].計算機應用研究，2021，38（3）：777-781.

[12] 程先云，程培澄，程培聰，等.優化擬合建模：1stOpt應用詳解[M].2版.北京：中國建材工業出版社，2019.

[13] 李春，劉澤民，陳恒杰，等.PeakFit、1stOpt在弗蘭克-赫茲實驗數據處理中的應用[J].大學物理實驗，2018，31（5）：117-123.