从N个项目中选择M个项目，以使完成这些M个项目的任务花费的时间最少

Question

我正在尝试解决以下问题：给您N个项目。每个项目包含三个任务A，B和C。完成任务A所需的时间为TA，任务B为TB，任务C为TC。现在，我们必须选择M项，以便完成这些M项的任务所需的时间最少。以下是规则：

1. 所有选择的M个项目同时运行，即所有M个项目的任务同时运行
2. 除非所有M个项目的任务A完成，否则无法启动任何选定项目的任务B
3. 除非所有M个项目的任务B完成，否则无法启动任何选定项目的任务C

例如：

if say N = 3 and M = 2 (it means we must select M items out of 3 items in total)
         Tasks: A  B  C
       item 1 : 1  2  2
       item 2 : 3  4  1
       item 3 : 3  1  2

如果选择项目1和项目3，则两个项目的任务A在3个单位后完成（项目1等待项目3完成），然后两个项目的任务B在接下来的2个单位时间后完成。同样，任务C在2个单位时间后完成。因此，总时间为7（这是我们可以找到的最小组合）

我尝试过考虑针对该问题的动态编程解决方案。但是我无法得到这个问题的具体解决方案。任何人都可以通过提供有效的解决方案来帮助我。

PS：请不要编写代码。我只是在这里寻找逻辑。

先感谢您。

Answer 1

通过贪婪方法求解（权重计算+截止日期排序）

这是解决此问题的贪婪方法，希望对您有所帮助。祝好运！

由于项目中的每个任务都需要时间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作为解决方案。

此数字将为我们提供所使用的最小插槽数。因此，这导致我们找到解决方案。