java - 从 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

现在让我们考虑一下；我们手中有 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 个位置

对于item2;8个插槽被占用

对于item3;6个插槽被占用

对于itemX；P槽被占用等等....

在知道每个项目在任务时间上需要的槽数后我们将检查 M 次减法作为项目组合在 N 次项目任务中以获得尽可能小的数量。

例子；当M=2时选择M项；

Item1-Item2 = 5;

Item1-Item3 = 3;

Item2-Item3 = 4;

**编辑； Item1 - Item2 对应所选项目数组合内减法的绝对值；例如如果 M=2； |a1-a2| + |b1-b2| + |c1-c2| ...

因此对于 M=2 个选择，我们取最小结果 3，这导致我们选择 Item1 和 Item3 作为解决方案。

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