有一个交叉点树的最优分派问题(Ⅰ)

An Algorithm for an Optimal Assignment Problem of Trees with Only One Cross Point (Ⅰ)

有n位机组人员,他们按其阅历形成只有一个交叉点的树。今欲把他们分成若干组,每组的人数是k+1,其中一位被指派作机长,其余k位被指派为组员。要求机长的阅历优于k位组员的阅历,而k位组员彼此之间的阅历的优劣不计。一位人员p担任机长时的贡献f(p),担任组员时的贡献为g(p),这里f(p)、g(p)是二个非负实值函数。自然有如下两个问题: 1.能把全体n位人员这样分组的充要条件是什么? 2.如果能把全体n位人员这样分组,问在所有可能的分组方法中哪种分组方法使得这n位人员的总贡献最大? 本文解决了第一个问题。

In this paper the following problem is considered. There are n crewmen. They are formed into trees with only one cross point according to their experiences. Now we divide them into several groups with K + l persons in each group in which only one is appointed captain and the others are members. The experience of the captain should be superior to those of other members in the group. Every person p is given two numbers f(P): g(P). When p is a captain his contribution is f(P). When p is a member, his contribution is g(P). Now we want to find an algorithm in order that the whole crew can make their greatest contribution. In this article we have solved the first part of the problem.