多维背包问题的启发式算法研究探讨.pdfVIP

2024年软件2024

第45卷第2期SOFTWAREVol.45,No.2

基金项目论文

多维背包问题的启发式算法研究探讨

王丽娜陆芷

（上海理工大学管理学院，上海200093）

摘 要：多维背包问题是NP难组合优化问题，其模型及算法近年来在众多领域得到了广泛应用。本文主要探讨多维背

包问题的启发式求解算法，通过对相关文献进行研究，阐述现有算法的优缺点，针对多维背包问题设计更高效的启发式求解算

法，为其提供新的思路和参考。

关键词：多维背包问题；组合优化；启发式算法

中图分类号：TP301.6 文献标识码：A DOI：10.3969/j.issn.1003-6970.2024.02.007

本文著录格式：王丽娜,陆芷.多维背包问题的启发式算法研究探讨[J].软件,2024,45(02):034-036

HeuristicAlgorithmsofMultidimensionalKnapsackProblem

WANGLina,LUZhi

(BusinessSchool,UniversityofShanghaiforScienceandTechnology,Shanghai200093)

【Abstract】：The multidimensional knapsack problem is an NP-hard combinatorial optimization problem, Its

model and algorithm has recently been widely used in many fields. This article mainly explores heuristic solving

algorithms for multi-dimensional knapsack problems, by studying relevant literature, elaborating on the advantages

and disadvantages of existing algorithms, designing more efficient heuristic solving algorithms for multi-

dimensional knapsack problems, and providing new ideas and references for them.

【Keywords】：multidimensional knapsack problem;combinatorial optimization;heuristic algorithms

0引言人们不断研究MKP的优化算法，希望开发出高效的解

组合优化问题是在有限可行解集合中寻找最优解的决方案，并且取得了一定进展。其中，启发式算法由于

一类离散优化问题，背包问题作为经典的组合优化问在可接受的时间范围内能够寻找到问题的最优或近似最

题，是组合优化问题的研究热点之一。最简单的0-1背优解决方案，近年来，在组合优化领域问题的求解中大

包问题关注背包在一维空间中物品的选择和优化，然而量涌现，将启发式算法用于求解MKP也取得了显著进展。

在实际应用中，通常需要考虑多种限制条件的情况。这因此，本文对MKP的启发式算法研究进行总结，

类需要考虑多维约束限制的背包问题称为多维背包问分析现有算法的性能及优缺点，为基于MKP设计更高