高性能计算机问题——2002年第12期题解

问题描述见2002年第12期杂志。算法分析本题是一个有实际应用背景的问题。第一步,我们不妨把题目中的多个节点简化成一个节点的特殊情况。在这样的情况下,我们已确定此节点的任务是《n_A,n_B)(n_A表示有n_A个A类子任务,n_B表示有n_B个B类子任务),那么,此节点所需的最短时间也就确定了,设这个最短时间为f_1(n_A,n_B)。下面我们把这种特殊情况推广到一般情况。在一般情况下,假设某一个节点i已分配的任务是(a_i,b_i)(a_i表示有a_i个A类子任务,b_i表示有b_i个B类子任务),那么,这第i个节点所确定的最短时间是f_i(a_i,