A heuristic solution procedure for the multiconstraint zero-one knapsack problem
提出一种利用替代对偶性的新启发式方法求解多约束背包问题，计算量随变量数多项式增长，测试中98%的问题解与最优解误差在1%以内，且优于其他启发式方法。
In this article a new heuristic procedure is proposed. This procedure makes use of surrogate duality in solving multiconstraint knapsack problems. Computational effort involved in the procedure is bounded by a polynomial in the number of variables. Extensive computational testing indicates that the procedure generates good feasible solutions regardless of the problem structure. In 98% of the problems solved, the solution generated by the heuristic was within 1% of the optimal solution. This procedure was also tested against other heuristics and was found to compare favorably.