Note—An Approximate Algorithm for Multidimensional Zero-One Knapsack Problems—A Parametric Approach
提出一种新的多维0-1背包问题近似算法，通过三个参数平衡解质量与计算时间，在48个测试问题中平均误差仅0.34%，且速度优于三种已知启发式算法。
A new approximate algorithm for multidimensional zero-one knapsack problems with all positive coefficients is presented. The procedure is controlled by three parameters which affect the tradeoff between solution quality and computation time and whose values are set by the users. For 48 test problems with 5 to 20 constraints and 6 to 500 variables, the solution found was on the average within 0.34% of the optimum and the computation time was the shortest compared with three other well-known heuristics.