Select N 项中的 M 项使得完成这 M 项的任务花费的时间最短
Select M items from N items such that completing these M item's tasks take the minimum time
我正在尝试解决以下问题：
给你 N 件物品。每一项包含三个任务A、B、C，完成任务A所需时间为TA，任务B为TB，任务C为TC。现在，我们必须 select M 项，以便完成这 M 项的任务花费最少的时间。规则如下：
- 同时操作所有select个M项，即同时操作所有M项的任务
- 任何 selected 项目的任务 B 无法启动，除非所有 M 项目的任务 A 完成
- 任何 selected 项的任务 C 都无法启动，除非所有 M 项的任务 B 都已完成
例如：
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
如果我们select项目1和项目3，两个项目的任务A在3个单位后完成（项目1等待项目3完成），然后两个项目的任务B在接下来的 2 个单位时间。同样，任务 C 在 2 个单位时间后完成。因此总时间为 7（这是我们可以找到的最小可能组合）
我试过想一个动态编程解决问题的办法。但我无法得到问题的具体解决方案。任何人都可以通过提供有效的解决方案来帮助我。
PS：请不要写代码。我只是在这里寻找逻辑。
提前致谢。
贪心法解法（权重计算+截止时间排序）
这里有一个解决这个问题的贪心法，希望对你有所帮助。祝你好运！
由于项目中的每个任务都需要时间 T 才能完成，我们可以将这些视为这些任务（A、B 和 C）的“最后期限”。我们可以将这些截止日期想象成 array/train 个槽中的“槽”。
为了形象化这些截止日期，请考虑这些示例；
项目 2 的任务 A；
0__A__1__A__2__A__3
项目 1 的任务 C；
0__C__1__C__2
现在让我们考虑一下；我们手中有 K 个“插槽”0__1__2__ ... __K，问题要求我们尽可能花费最少的插槽。
为了更好地可视化问题，您解释的另一个示例，当您选择 item1 和 item3 时，我们的插槽采用这种形式；
item1 + item3 "deadline slot occupation"
0_A_1_A_2_A_3_B_4_B_5_C_6_C_7
前三个槽被占用，因为item3的任务A比item1多了3个单位。任务 B 只能在这个“更长”的任务 A 完成后才能开始，因此从插槽号 3 开始。
于是问题就变成了这样；用花费的最少数量的插槽填充我们的插槽。因此，我们将采用贪婪的方法来解决这个问题。
- 为我们要从 N 个项目中选择的 M 个项目找到单独的“截止时间段”
在您提供的示例中；
对于 item1;
0_A_1_B_2_B_3_C_4_C_5
占用5个名额
对于项目 2;
已占用 8 个插槽
对于第 3 项；
已占用 6 个插槽
对于itemX;
P槽占用等等....
在知道每个项目在任务时间上需要的槽数后
我们将检查 M 次 减法 作为 N 次项目任务次数内的项目组合，以获得尽可能小的数量。
示例；
M=2时选择M项；
项目 1-项目 2 = 5;
项目 1-项目 3 = 3;
项目 2-项目 3 = 4;
**编辑； Item1 - Item2 对应所选项目数组合内减法的绝对值；例如如果 M=2； |a1-a2| + |b1-b2| + |c1-c2| ...
因此，对于 M=2 个选择，我们取最小结果 3，这导致我们选择 Item1 和 Item3 作为解决方案。
这个数字将告诉我们使用的最少插槽数。因此，这引导我们找到解决方案。
使用优先队列或排序的解决方案
假设我们选择了M个元素，A、B、C的最大值分别为Amax、Bmax和Cmax，那么我们可以确定数组中一定有某个元素A = Amax，对于B和C，所以我们可以说 A、B、C 最多有 N 个不同的值。因此 (Amax、Bmax、Cmax) 的可能组合最多为 N^3。然后我们可以检查数组中是否至少有 M 个元素满足每个组合的此约束，并使用 ans = max(ans, Amax + Bmax + Cmax) 更新答案值。这种方法需要 O(N^4) 时间。
但是我们可以使用排序或 Cmax 级别的优先级队列将时间复杂度降低到 O(N^3logN)。基本上，找到所有满足 Amax 和 Bmax 约束的元素并存储所有这些元素的 C 值，然后在数组中找到 Cmax 的第 M 个最小值。
我正在尝试解决以下问题： 给你 N 件物品。每一项包含三个任务A、B、C，完成任务A所需时间为TA，任务B为TB，任务C为TC。现在，我们必须 select M 项，以便完成这 M 项的任务花费最少的时间。规则如下：
- 同时操作所有select个M项，即同时操作所有M项的任务
- 任何 selected 项目的任务 B 无法启动，除非所有 M 项目的任务 A 完成
- 任何 selected 项的任务 C 都无法启动，除非所有 M 项的任务 B 都已完成
例如：
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
如果我们select项目1和项目3，两个项目的任务A在3个单位后完成（项目1等待项目3完成），然后两个项目的任务B在接下来的 2 个单位时间。同样，任务 C 在 2 个单位时间后完成。因此总时间为 7（这是我们可以找到的最小可能组合）
我试过想一个动态编程解决问题的办法。但我无法得到问题的具体解决方案。任何人都可以通过提供有效的解决方案来帮助我。
PS：请不要写代码。我只是在这里寻找逻辑。
提前致谢。
贪心法解法（权重计算+截止时间排序）
这里有一个解决这个问题的贪心法，希望对你有所帮助。祝你好运！
由于项目中的每个任务都需要时间 T 才能完成，我们可以将这些视为这些任务（A、B 和 C）的“最后期限”。我们可以将这些截止日期想象成 array/train 个槽中的“槽”。
为了形象化这些截止日期，请考虑这些示例；
项目 2 的任务 A；
0__A__1__A__2__A__3
项目 1 的任务 C；
0__C__1__C__2
现在让我们考虑一下；我们手中有 K 个“插槽”0__1__2__ ... __K，问题要求我们尽可能花费最少的插槽。
为了更好地可视化问题，您解释的另一个示例，当您选择 item1 和 item3 时，我们的插槽采用这种形式；
item1 + item3 "deadline slot occupation"
0_A_1_A_2_A_3_B_4_B_5_C_6_C_7
前三个槽被占用，因为item3的任务A比item1多了3个单位。任务 B 只能在这个“更长”的任务 A 完成后才能开始，因此从插槽号 3 开始。
于是问题就变成了这样；用花费的最少数量的插槽填充我们的插槽。因此，我们将采用贪婪的方法来解决这个问题。
- 为我们要从 N 个项目中选择的 M 个项目找到单独的“截止时间段”
在您提供的示例中；
对于 item1;
0_A_1_B_2_B_3_C_4_C_5
占用5个名额
对于项目 2; 已占用 8 个插槽
对于第 3 项； 已占用 6 个插槽
对于itemX; P槽占用等等....
在知道每个项目在任务时间上需要的槽数后 我们将检查 M 次 减法 作为 N 次项目任务次数内的项目组合，以获得尽可能小的数量。
示例； M=2时选择M项；
项目 1-项目 2 = 5;
项目 1-项目 3 = 3;
项目 2-项目 3 = 4;
**编辑； Item1 - Item2 对应所选项目数组合内减法的绝对值；例如如果 M=2； |a1-a2| + |b1-b2| + |c1-c2| ...
因此，对于 M=2 个选择，我们取最小结果 3，这导致我们选择 Item1 和 Item3 作为解决方案。
这个数字将告诉我们使用的最少插槽数。因此，这引导我们找到解决方案。
使用优先队列或排序的解决方案
假设我们选择了M个元素，A、B、C的最大值分别为Amax、Bmax和Cmax，那么我们可以确定数组中一定有某个元素A = Amax，对于B和C，所以我们可以说 A、B、C 最多有 N 个不同的值。因此 (Amax、Bmax、Cmax) 的可能组合最多为 N^3。然后我们可以检查数组中是否至少有 M 个元素满足每个组合的此约束，并使用 ans = max(ans, Amax + Bmax + Cmax) 更新答案值。这种方法需要 O(N^4) 时间。
但是我们可以使用排序或 Cmax 级别的优先级队列将时间复杂度降低到 O(N^3logN)。基本上，找到所有满足 Amax 和 Bmax 约束的元素并存储所有这些元素的 C 值，然后在数组中找到 Cmax 的第 M 个最小值。