本题故事由大语言模型生成。如有雷同,纯属巧合。
你刚加入一家知名自研 AI 公司。表面上风光无限,其实你知道:你的工作其实是反向工程了竞争对手
的模型,拼拼凑凑后贴上了自家 Logo 就发布了。
模型能用是能用. . . 但非非非常常常卡卡卡。CTO 怒不可遏,要你马上优化到不卡。
这个模型由 n 个紧密耦合的组件构成(都是借鉴的,所以你的团队里没人会优化)。这些组件之间存在
计算依赖关系,构成一个有向无环图。每个组件在其所有依赖组件完成后才能开始计算。
第 i 个组件需要 wi 毫秒来完成计算。一旦开始计算,它会在恰好 wi 毫秒后结束。
为了提速,你的任务是把计算过程划分成若干批:在任何时刻,只要满足依赖条件,你都可以并行执行
任意可用组件的非空子集。其中,可用组件是指在所有前置组件计算完成的组件。
在每一批中,所有被选中的组件必须一起执行完,才能进行下一批的计算。因此,每个批次的执行时长
由其中最慢的组件决定。
你的目标是安排整个执行过程,使得所有依赖条件都被满足,并使总耗时(即所有批的耗时之和)最
小。