背包问题的二分网格算法
A Dimidiate Grid Algorithm for the Unbounded Knapsack Problem作者机构：国家高性能计算中心
出 版 物：《计算机科学》 (Computer Science)
年 卷 期：2005年第32卷第6期
页 面：217-220页
核心收录：
学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 08[工学] 070105[理学-运筹学与控制论] 081201[工学-计算机系统结构] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）]
基 金：国家自然科学基金(60273075) 国家863高科技发展计划(863-306ZD-11-01-06)资助
主 题：背包问题 网格算法 二分 NP难问题 时间复杂性 精确算法 搜索方法 几何结构 指数增长 解空间 效益值 新算法 实例 无界 最优 数据
摘 要：本文介绍了属于NP难问题的无界背包问题的一种新的精确算法,基于问题的几何结构通过二分搜索方法不断减小解空间,最终直接求出问题的最优效益值和最佳装包方案。当待装入包中的物品数量固定时,算法的时间复杂性为线性时间,初步解决了求解当前呈指数增长背包实例时存在的困难,实验中各种数据实例证明与常用的MTU2和EDU相比,该新算法在理论上是可行的。
维普期刊数据库
同方期刊数据库