School of Engineering and Computer Science, Victoria University of Wellington, Kelburn, Wellington, New Zealand.
Faculty of Information Technology, Van Lang University, Ho Chi Minh City, Vietnam.
PLoS One. 2022 Apr 7;17(4):e0266537. doi: 10.1371/journal.pone.0266537. eCollection 2022.
While the classical knapsack problem has been the object to be solved by optimization algorithm proposals for many years, another version of this problem, discounted {0-1} knapsack problem, is gaining a lot of attention recently. The original knapsack problem requires selecting specific items from an item set to maximize the total benefit while ensuring that the total weight does not exceed the knapsack capacity. Meanwhile, discounted {0-1} knapsack problem has more stringent requirements in which items are divided into groups, and only up to one item from a particular group can be selected. This constraint, which does not exist in the original knapsack problem, makes discounted {0-1} knapsack problem even more challenging. In this paper, we propose a new algorithm based on salp swarm algorithm in the form of four different variants to resolve the discounted {0-1} knapsack problem. In addition, we also make use of an effective data modeling mechanism and a greedy repair operator that helps overcome local optima when finding the global optimal solution. Experimental and statistical results show that our algorithm is superior to currently available algorithms in terms of solution quality, convergence, and other statistical criteria.
虽然经典背包问题多年来一直是优化算法提案要解决的对象，但这个问题的另一个版本，折扣{0-1}背包问题，最近受到了很多关注。原始的背包问题要求从物品集中选择特定的物品，以最大化总收益，同时确保总重量不超过背包容量。而折扣{0-1}背包问题则有更严格的要求，其中物品被分为若干组，每组只能选择一个特定的物品。这种约束在原始背包问题中并不存在，使得折扣{0-1}背包问题更加具有挑战性。在本文中，我们提出了一种基于沙鱼群算法的新算法，以四种不同的变体形式来解决折扣{0-1}背包问题。此外，我们还利用了一种有效的数据建模机制和贪婪修复算子，帮助在寻找全局最优解时克服局部最优。实验和统计结果表明，我们的算法在解决方案质量、收敛性和其他统计标准方面优于现有的算法。
