基于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.