摘要
用数学方法分析了0/1背包问题的特性,提出了一个快速降价算法,该算法能成批确定一定在最优解中的物品和成批排除一定不在最优解中的物品。该算法既可单独使用,又可与启发式算法结合达到更好的结果。文中给出了应用实例及其分析。
Based on mathematical inference, this paper proposes a quick reduction algorithm for 0/1-knapsack problem. The algorithm can make certain which items would be in the best soltuion in batches and which items would not be. The algorithm not only can be used singly, but also can be combined with other heuristic algorithms to get better solutions. Series of examples and instances are solved and analysed.
出处
《系统工程理论方法应用》
北大核心
2005年第4期372-375,共4页
Systems Engineering Theory·Methodology·Applications
基金
国家自然科学基金资助项目(70471065)
上海市教委重点学科建设资助项目
关键词
0/1背包问题
快速降阶算法
上界
下界
0/1-knapsack problem
quick reduction algorithm
upper bound
lower bound
