中文核心期刊
CSCD来源期刊
中国科技核心期刊
RCCSE中国核心学术期刊
重庆交通大学学报（自然科学版）

重庆交通大学学报（自然科学版） ›› 1992, Vol. 11 ›› Issue (4): 107-114.

• • 上一篇    

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

刘莹   

  1. 基础部
  • 收稿日期:1991-03-29 出版日期:1992-08-24 发布日期:2016-11-08
  • 作者简介:刘莹,女,23岁,讲师

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

Liu Ying   

  1. Department of Basic Courses
  • Received:1991-03-29 Online:1992-08-24 Published:2016-11-08

PDF

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

关键词: 有一个交叉点的树, 可行性, 分派问题, 子, 父

Abstract: In this paper the following problem is considered. There are n crewmates. They forma tree with only one cross point according to their experiences. Now we divide them into several groups with k+1 persons in each group in which only one is assigned to be captain and the others are members. The captain's experience should be superior to those of the others in the group. Every person p is assigned two numbers f(p), g(p), When p is the captain, his contribution is f(p). When p is a member, his contribution is g(p). Now we have an algorithm to solve the problem that the whole crew makes its greatest contribution.

Key words: trees with only one cross point, feasibility, assignment problem, son, father