论文部分内容阅读
利用一种新方法即平衡技术来解答划分问题.证明若划分问题存在满足条件的子集,则该子集一定是平衡态.据此,仅对平衡进行枚举即可解答划分问题.若划分问题给定集合中每个元素的长度都被一个常数D界定,则实施动态规划技术且仅考虑平衡状态,解答划分问题的时间复杂度为0nD),即线性时间.该算法降低了划分问题原为(n<2>D)的复杂度.