Question

关于c++动态规划的问题

某一印刷厂有六项加工任务，对印刷车间和装订车间所需时间见下表（时间单
位：天）
任务 │J1 J2 J3 J4 J5 J6
─────┼───────────────
印刷车间│ 3 12 5 2 9 11
装订车间│ 8 10 9 6 3 1
如何安排加工顺序，使加工时间最少

我要的不仅仅是代码，还有解体的思路，思路思路，一定要有思路，请把思路写详细一点，谢谢

• 你的回答被采纳后将获得：
• 系统奖励15（财富值+成长值）+难题奖励30（财富值+成长值）

Answer 1

题目中较明显的条件：

1. 每项任务，只有在印刷车间完成后，才能在装订车间加工。
   

2. 第一个任务完成前，装订车间不开工

很明显，安排印刷车间的任务，要将印刷车间工作天数比装订车间工作天数小的安排在前面。

如此任务分两类

印刷车间工作天数 < 装订车间工作天数：j1,j3,j4   ①

印刷车间工作天数 > 装订车间工作天数：j2,j5,j6   ②

到这，已经完全可以用枚举算法。当然，你还可以再进一步：

①中你可以再继续排序，依据印刷车间工作天数从小到大排序，这样就是： j4, j1, j3

我们确定了j4做为印刷车间第一个任务。

然后根据 j4装订车间工作天数 - j4印刷车间工作天数 所得出的值，继续求第二个任务。

这样三个任务安排方法就出来了。

②与①很类似，是①的反向思考了，这里就不多说。

问题不是很复杂，讲到这思路也差不多，再讲下去，代码直接就出来了。