论文部分内容阅读
设有整数集Ｓ＝｛ｒ１，ｒ２；ｐ１，ｐ２，…，ｐｎ｝，这里ｒｉ≥０，ｐｊ＞０（ｉ＝１，２；ｊ＝１，２，…，ｎ），寻找一个Ｓ的最优分划Ｐ＝（Ｓ＊１，Ｓ＊２）使得：（１）ｒｉ属于不同子集，（２）Ｓ＊１与Ｓ＊２中元素总和较大者尽可能地小．这是一个ＮＰ－完备问题，本文给出一个线性时间近似算法，它的近似界为８７．