Abstract: Multidimensional 0-1 knapsack problem often appears in decision making and programming, resource distribution, loading, and so on. For solving this problem, many algorithms such as simulated annealing, genetic algorithm, ant colony algorithm, and other heuristic algorithms have been proposed by scholars. In this paper, a quasi-human heuristic algorithm for 0-1 knapsack is proposed. The algorithm utilizes two important strategies, i.e., how to select the item based on its average value and how to escape the trap. 55 multidimensional 0-1 knapsack test instances are tested by the produced algorithm, 54 instances of them achieve optimum solutions. The integrated performance of the produced algorithm is rather satisfied, and the runtime is short. Experimental results demonstrate that the algorithm proposed in this paper is rather efficient for solving multidimensional 0-1 knapsack problem.

Key words: Knapsack problem, Value selection, Trap escaping strategy, Quasi-human heuristic algorithm

摘要： 在项目决策与规划，资源分配，货物装载等工作中，提出了多维0-1背包问题，对这一问题，国内外学者提出了诸如模拟退火算法，遗传算法，蚁群算法及其它一些启发式算法等求解算法。本文提出了一种新的启发式求解算法。该算法使用了两个主要的思想策略，即依据物品单位容积价值的高低选择物品并对其进行标记的策略和拟人跳坑策略。用本文提出的算法，对55个测试算例进行了实算测试，得到了其中54个算例的最优解。测试结果表明，用本文提出的拟人算法求解多维0-1背包问题，计算结果的优度高，计算时间短，是求解此问题的有效算法。

关键词: 背包问题, 价值选择, 跳坑, 拟人算法