论文部分内容阅读
本文的工作是Baker，Smith，Agentis等人的研究工作的发展。研究的目标函数有Cmax，∑Cj，Lmax，maxWjCj，∑WjCj以及maxVj。主要结果如下：定理1问题1‖∑Cj+maxW′iC′i是多项式时间可解的，算法如下：Step1令u：=n1，v：=n2，F：=0.Step2如果u=0，则定义π(i)=J′i，1≤i≤v，停止.Step3如果v=0，则定义π(i)=Ji，1≤i≤u，令F：=F+∑t(i，0)，停止.Step4若maxW′vt(u，v)＞y，则定义π(u+v)=Ju，令u：=u-1，F：=F+t(u，v)；转Step2.若maxW′vt(u，v)≤y，则定义π(u+v)=J′v，令v：=v-1；转Step2。定理2问题1‖∑Ci：maxW′iC′i是多项式时间可解的，算法如下：Step1令u：=n1，v：=n2.Step2若u=0，则定义π(i)=J′i，1≤i≤v，停止.Step3若v=0，则定义π(i)=Ji，1≤i≤u，停止.Step4若maxW′ct(u，v)＞y，则定义π(u+v)=Ju，令u：=u-1转Step2.若maxW′vt(u，v)≤y，则定义π(u+v)=J′v，令v：=v-1；转Step2。定理3问题1‖∑WjCj+maxW′jC′j是强NP-困难的。定理4问题1‖∑WjCj≤Q：∑V′j≤0是强NP-困难的。定理5问题1‖∑WjCj+WmaxVj是强NP-困难的。定理6问题1‖(C(1)max，C(2)max，…，C(k-1)max，L(k)max)在系数θi均为1的情形是多项式时间可解的。定理7问题1‖(C(1)max，…，C(r)max，∑Wj(r+1)Cj(r+1)，…，∑Wj(k)Cj(k))是多项式时间可解的。