编程沙龙（16）
IT商界
本月题目：
若由两个人A、B承担N个作业的任务。设第i个作业交给A处理需要的时间为ai，而交给B处理，需要的时间为bi。由于各作业的特点和各人擅长的技能不同的关系，很可能对于某些i，有ai≥bi，而对于某些j，j≠i，有aj＜bj。既不能将一个作业分开由两个人处理，也没有一个人能同时处理两个作业。设计一个算法，使得这两个人处理完这N个作业的时间最短(从任何一个人开工到最后一个人完工的总时间)。研究一个实例：(a1,a2,a3,a4,a5,a6,a7)=(2,8,9,11,4,5,7)；(b1,b2,b3,b4,b5,b6,b7)=(4,5,12,10,3,4,8)。
从读者朋友们参加有奖征答寄来的程序看，有少部分朋友可能没完全理解题目的意思。由于我们没有规定完成工作的顺序性要求，也就是可以存在并行的操作，所以我们解题时就不能简单地依次比较每项工作两人的用时长短，由用时短的来完成该项任务。另外，由于采用并行工作的方式，所以计算合计时间时，要考虑并行处理的时间不可以重复叠加。例如：完成两项工作，A=(2,3)，B=(5,4)。正确的解应该是，由A完成第1项工作，由B完成第2项工作，总的用时是4。首先，尽管A做第2项工作用时比B要短，但由于A已经在做第1项工作，所以如果让B同时去做第2项工作时，可以充分利用到两人并行工作时的重叠时间。(你可以比较一下其他任何的分配方式，都不会比这种方法来的少)
另外，还有不少朋友理解了题意，也注意到了并行处理的时间重叠的问题，但在解题时没有把问题想全面。我归纳了一下，这部分问题可以归为三种样式：
一、比较连续的两项工作，考虑重叠时间对总时间的影响。这类的解题思路是：依次确定每项工作交由谁来完成。选定第i项工作由谁来完成后，就将另一人的第i+1项工作用时减掉前一项的工作用时，再来比较第i+1项工作谁的用时少。如果是第1项工作，就直接选取用时少的那个。就以我们题目中实例为例：A=(2,8,9,11,4,5,7)，B=(4,5,12,10,3,4,8)。很显然第1项工作由A来做，用时2。接着将B的第2项工作用时5减去2得3，再来比较A、B做第2项工作的用时8和3，这样就是B来做第2项工作，用时3(考虑并行作业的时间重叠)。再接着将A的第3项工作用时9减去3得6，再比较A、B第3项工作得用时……以此类推。由于第1项工作的分配只是简单比较谁用时短就由谁来做，所以在一些情况下存在问题。就用上面A=(2,3)B=(5,4)例子来说，如果将两项工作的序号进行颠倒变成A=(3,2)B=(4,5)，那么最终的总用时就变成是5，而不是4。
二、考虑累计时间和。这类的解题思路是：用两个变量如Ta、Tb分别记录在第i项工作分配前，A、B两人累计的工作用时。当分配第i项工作时的分配原则是：比较Ta+ai与Tb+bi，将任务交给总用时少的那个，并累计Ta、Tb。其实这种解题思路也同样存在上面说到的由于第1项工作的分配方式而带来的问题。
三、这第三类的解题思路是指使用一些特殊的比较因子，如考察每项工作两人的工作差，还如考察每项工作两人的总工作时间，并进行排序等等。这类的解题思路千差万别，但都很新颖，有些还是很有创意的并有一定理论依据的。但利用检测数据检测的结果，好像还没有完全正确的。(为了尽可能不造成错判，检查这些程序源码，用去了我大量的时间。看着一旁怒目而视的MM，冷汗……)
好了，说完有问题的。我们来看看究竟该怎么来解这道题。上期沙龙里我讲了利用穷举搜索的方式是可以解题的，这次也有不少朋友是使用了这种办法。而且朋友们用的具体办法还各不相同，有用递归的，有不用递归用一个FOR循环就解决问题的。但由于这类办法思路比较简单，效率不是太好(特别是工作的数量较多时)，所以我们在这里不具体分析这种方法。在源码下载中，我们会提供相关源码。
下面是本题的分析与解答：
根据题目的意思，使用动态规划算法的思想，我们可以考虑由对每个工作i，依次计算集合S(i)。其中每个集合中的元素都是3重组(F1,F2,x)。其中F1是A的完成时间；F2是B的完成时间；x是任务分配方案(令xi=1时表示将任务i分配给A，当xi=0时表示将任务分配给B)。初始时，S(0)={(0,0,0)}。令F=按处理时间少的原则来分配任务的方案所需的完成时间。然后，依次考虑任务i，i=1～N。在分配任务i时，只有两种情形，xi=0或xi=1。此时，令S(i)={ S(i)+(ai,0,2i)}∪{ S(i-1)+(0,bi,0)}。在做集合并集计算时，遵循下面的原则：
a.当(a,b,c),(d,e,f)∈S(i)且a=d,b≤e时，仅保留(a,b,c)
b.仅当max{a,b}≤F时，(a,b,c)∈S(i)
最后在S(N)中找出使max{F1,F2}达到最小的元素，相应的x即为所求的最优解，其最优值为max{F1,F2}。
由于版面问题，所以本期不刊出解题源码。本期有奖征答的解题源码下载地址：http://paladin.nease.net/cpcw/work.zip 。
获奖名单：
天津市河西区永安道德恩里小区1-1-302 李 超
河北省邢台市拐角东路5号教学仪器厂 张延波
天津市南开区科研西路2号金辉大厦 503宿 何 健
他们将分别获得赛门特克公司提供的《诺顿网络安全特警2003简体中文版》正版软件一套。
幸运读者：
安徽 汪阐、四川 李强、湖北 郭其中
他们分别可获得《VB6/.NET编程实例精选》一书。