通过贪婪方法求解(权重计算+截止日期排序)
这是解决此问题的贪婪方法,希望对您有所帮助。祝好运!
由于项目中的每个任务都需要时间T才能完成,因此我们可以将其视为这些任务(A,B和C)的“最后期限”。我们可以将这些截止日期可视化,就好像它们是插槽阵列/系列中的“插槽”一样。
为了可视化这些截止日期,请考虑以下示例;
项目2的任务A;
0__A__1__A__2__A__3
项目1的任务C;
0__C__1__C__2
让我们现在考虑一下;我们的手0__1__2__ … __K内有K个“插槽”,该问题要求我们尽可能减少插槽的使用量。
为了更好地可视化问题,从您的说明中得到的另一个示例是,当您选择item1和item3时,我们的广告位采用了这种形式;
item1 + item3“截止时间槽占用”
0_A_1_A_2_A_3_B_4_B_5_C_6_C_7
前三个插槽被占用,因为item3的任务A比item1长3个单位。任务B仅在完成“较长”任务A后才能启动,因此从插槽号3开始。
因此问题就变成了这个。在我们的广告位中填满最少要使用的广告位。因此,我们将对此问题采取贪婪的态度。
- 从我们要从N个项目中选择的M个项目中找到单独的“最后期限广告位”
在示例中,您提供了;
对于项目1;
0_A_1_B_2_B_3_C_4_C_5
占用5个插槽
对于项目2; 占用8个插槽
对于第3项; 占用6个插槽
对于itemX; P插槽已占用,等等。
在知道每个项目对任务时间要求的插槽数量之后,我们将在N个项目任务时间之内检查M个 减法 项作为项目的组合,以获取最小的数量。
例; 当M = 2时选择M个项目;
Item1-Item2 = 5;
Item1-Item3 = 3;
Item2-Item3 = 4;
**编辑; 项目1-项目2对应于所选项目数量组合中的减法绝对值;例如,如果M = 2;| a1-a2 | + | b1-b2 | + | c1-c2 |
…
因此,对于M = 2个选择,我们取最小值3,这导致我们选择Item1和Item3作为解决方案。
此数字将为我们提供所使用的最小插槽数。因此,这导致我们找到解决方案。



