解答划分问题的新拟多项式时间算法

• 作者: 朱大铭 雷鹏
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 划分问题 平衡 子集 动态规划
• 年，卷（期）: 2005,（32）
• 所属期刊栏目: 学术探讨
• 页码范围: 56-57,99
• 页数: 3页
• 分类号: TP301.6
• 字数: 2823字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2005.32.018

摘要

利用一种称为平衡技术的新方法解答划分问题.证明若划分问题存在满足条件的子集,则该子集一定是平衡集,仅对平衡集进行枚举即可解答划分问题.若划分问题给定集合中每个元素的长度都被一个常数M所界定,结合动态规划技术且仅考虑平衡集,解答划分问题的时间复杂度为O(nM),此算法在时间效率上对现有算法有较大改进.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	朱大铭	山东大学计算机学院	50	263	11.0	13.0
2	雷鹏	烟台师范学院计算机科学与技术学院	2	0	0.0	0.0